P4137 Rmq Problem / mex

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

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 $m$ lines, one number per line, giving the answer to each query in order.

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