Find the Mex in Subarrays

Given an array of length \(n\), denoted as \(\{a_1,a_2,\ldots,a_n\}\), and \(m\) queries, each query asks for the smallest natural number (i.e. the smallest non-negative integer) that does not occur in the specified subarray. Formally, for a query with indices \(l\) and \(r\) (1-indexed), find

[ \mbox{mex}({a_l,a_{l+1},\ldots,a_r\}) = \min { x \in \mathbb{N} : x \notin {a_l,a_{l+1},\ldots,a_r}}. ]

The input begins with two integers \(n\) and \(m\). The next line contains \(n\) space-separated integers representing the array. Each of the following \(m\) lines contains two integers \(l\) and \(r\) (1-indexed), representing a query. For each query, output the corresponding mex on a new line.

inputFormat

The first line contains two integers \(n\) and \(m\) (the size of the array and the number of queries). The second line contains \(n\) space-separated integers \(a_1,a_2,\ldots,a_n\). Each of the next \(m\) lines contains two integers \(l\) and \(r\) indicating the range (1-indexed) for a query.

outputFormat

For each query, output the smallest non-negative integer (mex) that does not occur in the subarray from index \(l\) to \(r\). Each answer should be printed on a new line.

sample

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

3
0
5