verkhoyansk

Verkhoyansk

== 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

6 8
6 9
6 10

| 0

| 1
6
5
3
3
8
4
8
8
5
5
8
8
1
3
3

|
| 16 32
8 7 6 5 2 1 8 7 1 2 3 4 5 6 3 4

3 5
1 14
2 14

| 0

| 9
1
3
9
1
3
9
9
4
1
4
5
9
4
9
9
8
3
1
3
1
4
9
9
1
3
9
3
9
3
9
9

|
h3. Tutorial

You can see a solution description in problem's 'editorial':verkhoyansk/solutie
 
h3. Request
 
Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.

Puteti vedea solutia problemei la 'editorial':verkhoyansk/solutie_romana

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