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

Poveste şi cerinţă...

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.

h2. Date de intrare

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

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

h2. Input

h2. Date de ieşire

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

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

h2. Output

h2. Restricţii

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 |

| 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

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

|

h3. Tutorial
 
You can see a solution description in problem's 'editorial':verkhoyansk/solutie
 
h3. Request

h3. Explicaţie

Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.

...

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