Runda 20 [Hard] - Bokserzy

17.05.2011 - Damian Rusak

Zadanie tygodnia

runda 20; kategoria Hard

Limit czasowy: 5s; Limit pamięciowy: 128MB

Bokserzy

Nadchodzi czas wielkich mistrzostw jednej z niezliczonych federacji bokserskich. Ta federacja szczyci się tym, że walki na jej mistrzostwach są absolutnie uczciwe - nikt nie sprzedaje walk, liczą się tylko umiejętności. Perfekcja i niezawodność zawodników doprowadziła jednak do tego, że wyniki każdej walki są do przewidzenia - każdemu zawodnikowi można przypisać pewną liczbę $C_{i}$ - obrazującą poziom jego umiejętności. Jeśli w walce mierzą się dwaj zawodnicy, zwycięża zawsze ten, któremu przypisana liczba jest większa. W przypadku równych poziomów walka kończy się remisem.

Widzowie jednak nie znają zawodników dobrze i ich poziom jest dla nich tajemnicą. Zachodzą w głowę, jakie mogłyby być wyniki spotkań. Pytają Ciebie (znanego promotora) o możliwe osiągi pewnych bokserów. Bokserom przydzielono przed mistrzostwami numery od $1$ do $n$ . Pytania są postaci : "Gdyby zawodnik $x$ walczył z każdym z zawodników z przedziału od $a$ do $b$ (włącznie) to z iloma by wygrał, a z iloma zremisował?". Aby zwiększyć zainteresowanie mistrzostwami pomóż im szybko poznać odpowiedź!

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę $n$ - liczbę zawodników ( $1 \leq n \leq 200000$ ). W kolejnej linii znajduje się $n$ liczb całkowitych $C_{1}$ , $C_{1}$ , ... , $C_{n}$ - liczb obrazujących umiejętności kolejnych zawodników. ( $1 \leq C_{i} \leq 10^{9}$ ). W kolejnej linii znajduje się liczba $k$ - liczba zapytań. ( $1 \leq k \leq 15000$ ). W kolejnych $k$ liniach znajdują się trójki liczb $x_{j}$ , $a_{j}$ $b_{j}$ - oznaczających, że pytamy o wynik walki zawodnika o numerze $x_{j}$ ze wszystkimi zawodnikami z przedziału $[a_{j}, b_{j}]$ . ( $1 \leq x_{j} \leq n, 1 \leq a_{j} \leq b_{j} \leq n$ ).

Wyjście:

Dla każdego kolejnego zapytania na wyjściu powinny znaleźć się dwie liczby całkowite - odpowiednio liczba zawodników z zadanego przedziału z którymi wygrałby zawodnik $x_{j}$ oraz liczba zawodników z którymi zremisowałby. Oczywiście nie należy wliczać do odpowiedzi (trudnego do wyobrażenia) pojedynku zawodnika samego ze sobą, o ile należy on do przedziału z zapytania.

Przykład:

Wejście:

3 5 2 4 4 4

2 4 6

6 3 6

3 1 2

Wyjście:

3 0

1 2

0 0

Wyjaśnienie: W pierwszym zapytaniu zawodnik $2$ ma poziom umiejętności $C_{2}=5$ , zatem zwycięża ze wszystkim zawodnikami z przedziału $[4,6]$ , nie remisując z nikim. W drugim zapytaniu zawodnik $6$ nie walczy z samym sobą, ale zwycięża z zawodnikiem nr $3$ i remisuje z zawodnikami $4$ i $5$ . W trzecim zapytaniu zawodnik nr $3$ przegrywa z oboma zawodnikami z zadanego przedziału.