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

Poveste şi cerinţă...

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.

h2. Date de intrare

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.

Fişierul de intrare $verkhoyansk.in$ ...

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$.

h2. Date de ieşire

h2. Input

În fişierul de ieşire $verkhoyansk.out$ ...

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$.

h2. Restricţii

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.
 
h2. Constraints
 
* $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"

h2. Exemplu
table(example). |_. verkhoyansk.in |_. verkhoyansk.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 14 16
3 4 3 2 5 1 6 7 2 1 6 2 4 3
0 4
0 5
9 13
9 12
3 12
2 12
2 11
1 11
3 13
5 13
8 13
0 7
0 8
6 8
6 9
6 10
| 0
|
| 16 32
8 7 6 5 2 1 8 7 1 2 3 4 5 6 3 4
1 14
0 2
2 5
1 13
12 14
1 9
5 14
1 15
5 10
2 2
4 10
5 11
5 13
0 10
0 15
1 13
7 15
3 6
12 14
3 5
14 14
2 10
0 12
2 15
0 0
4 8
0 12
0 7
6 15
3 5
1 14
2 14
| 0

|

h3. Explicaţie

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.

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