== include(page="template/taskheader" task_id="verkhoyansk") ==
Marcel has planned a trip in the Verkhoyansk Range, a 1200 km mountain range in the Sakha Republic. The landscape can be seen as an array of $N$ integers with values between $1$ and $N$, representing the heights of the mountain peaks along the range.
Marcel a planuit o excursie in Muntii Verkhoyansk, un lant muntos de 1200 de kilometri in Republica Sakha. Peisajul poate fi vazut ca un vector de $N$ numere naturale, cu valori intre $1$ si $N$, reprezentand inaltimile varfurilor muntoase ale lantului.
Marcel has $Q$ friends. Friend $i$ will visit all peaks with indices from $L[i]$ to $R[i]$. Marcel wants to know, for each of them, what is the smallest positive integer height of a peak each friend will not visit. He needs to know this in order to optimally plan his next trip.
Marcel are $Q$ prieteni. Prietenul $i$ va vizita toate varfurile cu indicii intre $L[i]$ si $R[i]$ inclusiv. Marcel vrea sa stie, pentru fiecare dintre ei, care este cea mai mica inaltime a unui varf, numar natural pozitiv, pe care fiecare prieten *nu* o va vizita. El trebuie sa stie asta pentru a-si planifica in mod optim urmatoarea lui excursie.
For example, if one friend visits peaks with heights $3$ $2$ $5$ $1$ $1$ $6$ $3$ $5$, the smallest positive integer height of a peak he didn't visit is $4$.
De exemplu, daca un prieten viziteaza varfurile cu inaltimile $3$ $2$ $5$ $1$ $1$ $6$ $3$ $5$, cea mai mica inaltime naturala pozitiva a unui varf pe care el nu a vizitat-o este $4$.
h2. Input
The first line of the input file $verkhoyansk.in$ contains numbers $N$ and $Q$. The second line contains $N$ integers with values between $1$ and $N$, representing the heights of mountain peaks. The following $Q$ lines contain 2 numbers, $L[i]$ and $R[i]$, with $0 ≤ L[i] ≤ R[i] ≤ N - 1$.
Pe prima linie a fisierului de intrare $verkhoyansk.in$ se vor afla numerele $N$ si $Q$. Pe a doua linie se afla $N$ numere naturale cu valori intre $1$ si $N$, reprezentand inaltimile varfurilor muntoase. Urmatoarele $Q$ linii contin fiecare cate 2 numere, $L[i]$ si $R[i]$, cu $0 ≤ L[i] ≤ R[i] ≤ N - 1$.
h2. Output
In the output file $verkhoyansk.out$ there will be $Q$ lines. Line $i$ contains the smallest positive integer height of a peak friend number $i$ will not visit.
In fisierul de iesire $verkhoyansk.out$ se vor afla $Q$ linii. Pe linia $i$ se afla cea mai mica inaltime, numar natural pozitiv, pe care prietenul cu numarul $i$ *nu* o va vizita.
h2. Constraints
h2. Restrictii si precizari
* $1 ≤ N ≤ 300.000, 1 ≤ Q ≤ 600.000$
* For $8$ points, $N ≤ 1.000, Q ≤ 10.000$
* For other $8$ points, $N ≤ 100.000, Q ≤ 200.000$ and all the heights are at most $50$
* For other $56$ points, $N ≤ 100.000, Q ≤ 200.000$
* Note that the scoring is not the same as the one in the official onsite contest
* Note that the array of heights is "0-indexed"
* Pentru $8$ puncte, $N ≤ 1.000, Q ≤ 10.000$
* Pentru alte $8$ puncte, $N ≤ 100.000, Q ≤ 200.000$ si toate inaltimile sunt mai mici sau egale cu $50$
* Pentru alte $56$ puncte, $N ≤ 100.000, Q ≤ 200.000$
* Distributia scorului e diferita de cea din timpul concursului oficial.
* Vectorul inaltimilor incepe cu pozitia 0.
* Putem observa ca Marcel are foarte multi prieteni.
* 0 nu este nici pozitiv si nici negativ.
h2. Exemplu
