Se dă un șir ordonat crescător a1, a2, …, an de numere întregi. Asupra șirului putem efectua trei tipuri de interogări:

• 1 x – Câte numere din șir sunt mai mici sau egale decât x?
• 2 x – Câte numere din șir sunt mai strict mai mari decât x?
• 3 x – De câte ori apare în șir valoarea x?

Cerința

Să se răspundă la Q interogări.

Date de intrare

Fișierul de intrare cb1.in conține pe prima linie numărul n, pe a doua linie n numere naturale separate prin câte un spațiu, elementele șirului. Pe a treia linie se află un număr natural Q, iar pe următoarele Q linii se găsesc câte două numere op x, unde op este numărul operației.

Date de ieșire

Fișierul de ieșire cb1.out va conține exact Q linii. Pe fiecare linie i, i=1..Q, se va afla un singur număr natural reprezentând răspunsul la a i-a interogare.

Restricții și precizări

• 1 ≤ n ≤ 50.000
• 3 ≤ Q ≤ 100.000
• numerele din șir sunt în ordine crescătoare și sunt cuprinse între -1.000.000.000 și 1.000.000.000.

Exemplu:

cb1.in

10
-2 4 4 4 7 7 7 7 8 11
4
1 5
2 5
3 7
3 9

cb1.out

4
6
4
0

Explicație

Prima interogare, 1 5: câte numere din șir sunt mai mici sau egale decât 5?. Răspunsul este 4
A doua interogare, 2 5: câte numere din șir sunt strict mai mai mari decât 5?. Răspunsul este 6
A treia interogare, 3 7: de câte ori apare în șir valoarea 7?. Răspunsul este: de 4 ori.
A patra interogare, 3 9: de câte ori apare în șir valoarea 0?. Răspunsul este: de 0 ori.