intrebari

La finalul concursului de alergare organizat de ziua orașului, rezultatele au fost afișate în ordine alfabetică după numelor participanților.
Dan dorește să participe și el la competiție anul viitor și, vâzând lista începe să își pună diverse întrebări.
Întrebare de tipul $1$: Dacă aș fi obținut punctajul $x$, câți concurenți ar fi avut punctajul strict mai mic decât al meu?
Întrebare de tipul $2$: Dacă aș fi obținut punctajul $x$, câți concurenți ar fi avut punctajul egal cu al meu?
Întrebare de tipul $3$: Dacă aș fi obținut punctajul $x$, câți concurenți ar fi avut punctajul strict mai mare decât al meu?

Cerință

Voi aveți de scris un program care să ofere repede răspuns la întrebările lui Dan.

Date de intrare

În fișierul de intrare intrebari.in se află pe prima linie numărul de concurenți, notat de noi cu $n$, iar pe linia a doua (în ordinea afișării de către organizatori) timpul în care fiecare concurent a parcurs traseul, ca număr natural, exprimat în secunde.
Pe linia a treia se află numărul de întrebări puse de Dan, notat de noi cu $m$.
Pe fiecare din următoarele $m$ linii se află câte două numere naturale $T$ și $x$, separate prin spațiu. $T$ reprezintă tipul de întrebare (poate fi $1$, $2$, $3$) iar $x$ reprezintă punctajul pentru care se dorește aflarea de informații.

Date de ieșire

În fișierul de ieșire intrebari.out se află $m$ numere naturale, câte unul pe rând, reprezentând, în ordinea de la intrare, răspunsul pentru câte o întrebare.

Restricții și prezicări

• $1 \leq n \leq 100 \ 000$;
• $1 \leq m \leq 100 \ 000$;
• Punctajele obținute de concurenți și valorile $x$ sunt numere naturale cuprinse între $1$ și $1 \ 000 \ 000 \ 000$ (un miliard), inclusiv.
• Pentru $18$ de puncte toate întrebările sunt de tip $1$.
• Pentru alte $18$ de puncte toate întrebările sunt de tip $2$.
• Pentru alte $18$ de puncte toate întrebările sunt de tip $3$.
• Pentru restul de $46$ de puncte testul conține întrebări de toate tipurile.
• Pentru $34$ de puncte toate numerele din fișierul de intrare sunt cel mult egale cu $1\ 000$.
• Pentru $76$ de puncte toate numerele din fișierul de intrare sunt mai mici sau egale cu $100\ 000$.

Exemplul 1

intrebari.in

5
4 1 8 1 6
3
1 3
1 4
1 10

intrebari.out

2
2
5

Exemplul 2

intrebari.in

5
4 1 8 1 6
3
1 3
2 4
3 10

intrebari.out

2
1
0