Mex

Problem Description

You have an array $a_1, a_2, \dots ,a_n$ of length $n$.

You must answer $q$ queries. Each query gives an interval $[l, r]$ and asks for the smallest natural number that does not appear in this interval.

Input Format

The first line contains two numbers $n, q$ ($1\leq n, q\leq 2\times 10^5$).

The next line contains $n$ numbers $a_1, a_2, \dots, a_n$ ($0\leq a_i\leq 10^9$).

The next $q$ lines each contain two integers $l, r$ ($1\leq l\leq r \leq n$).

Output Format

For each query, output one number on a single line, the answer.

Sample Input

5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5

Sample Output

1
2
3
0
3