Description

There is an array $\{a_1,a_2,\ldots,a_n\}$ of length $n$.

There are $m$ queries; for each query, find the smallest non-negative integer that does not appear in the interval (mex).

Input Format

The first line contains two positive integers $n,m$.
The second line contains $n$ non-negative integers $a_1, a_2, \ldots , a_n$.
Then follow $m$ lines, each containing two positive integers $l,r$, representing a query.

Output Format

Output $m$ lines, one number per line, giving the answer to each query in order.

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

1
2
3
0
3

Hint

For $30\%$ of the testdata: $1\leq n,m\leq 1000$.
For $100\%$ of the testdata: $1\leq n,m\leq 2\times {10}^5$, $1\leq l\leq r\leq n$, $0\leq a_i\leq 2\times 10^5$.

Translated by ChatGPT 5