== include(page="template/taskheader" task_id="cautbin") ==

Se da un sir de numere ordonat cu $n$ elemente, si se cere sa se raspunda la $M$ intrebari de tipul:
0 $x$ - pozitia cea mai mare pe care se afla elementul cu valoarea $x$ sau $-1$ daca nu se gaseste in sir
1 $x$ - pozitia pe care se afla elementul cel mai mare mai mic sau egal cu $x$ in sir
2 $x$ - pozitia pe care se afla elementul cel mai mic mai mare sau egal cu $x$ in sir

Fie un sir cu $N$ numere naturale ordonate crescator. Se cere sa se raspunda la $M$ intrebari de tipul:
$0 x$ - raspunsul va fi egal cu cea mai mare pozitie pe care se afla elementul cu valoarea $x$ sau $-1$, daca acesta nu se gaseste in sir
$1 x$ - pozitia in sir pe care se afla elementul cel mai mare mai mic sau egal cu $x$
$2 x$ - pozitia in sir pe care se afla elementul cel mai mic mai mare sau egal cu $x$

h2. Date de intrare

Pe prima linie a fisierului de intrare $cautbin.in$ se afla numarul $N$ reprezentand numarul de elemente alea sirului. Pe urmatoarea linie se gasesc $N$ numere reprezentand elementele sirului. Linia a treia contine numarul $M$ reprezentand numarul de intrebari. Apoi urmeaza $M$ linii, fiecare cu unul dintre cele 3 tipuri de intrebari.

Pe prima linie a fisierului de intrare $cautbin.in$ se afla numarul $N$ reprezentand numarul de elemente ale sirului. Pe urmatoarea linie se gasesc $N$ numere reprezentand elementele sirului. Linia a treia contine numarul $M$, reprezentand numarul de intrebari. Apoi urmeaza $M$ linii, fiecare linie descriind cate o intrebare de tipul celor precizate mai sus.

h2. Date de iesire

In fisierul de iesire $cautbin.out$ se vor afisa $M$ linii reprezentand raspunsul la cele $M$ intrebari.

In fisierul de iesire $cautbin.out$ se vor afisa $M$ linii reprezentand raspunsurile la cele $M$ intrebari.

h2. Restrictii

* $1 ≤ $N$ ≤ 100000$
* $1 ≤ $M$ ≤ 100000$
* Elementele sirului se vor incadra pe 31 de biti

* $1 ≤ $N$ ≤ 100 000$
* $1 ≤ $M$ ≤ 100 000$
* Elementele sirului se vor incadra pe $31$ de biti
* Elementele sirului sunt numerotate incepand cu $1$

h2. Exemplu

  1 2
  2 7
| 2

  2
  3

  1
  4

|
h2. Indicatii de rezolvare

Probleme care se rezolva cu cautarea binara:

* Infoarena 'nrtri':/problema/nrtri

* Infoarena "nrtri":http://infoarena.ro/problema/nrtri

== include(page="template/taskfooter" task_id="cautbin") ==