小象得到了一个0 \sim n-1的排列 a，并且得知了一个新的函数 mex。mex(S)的值为整数集合 S 中未出现的最小自然数。

此时 小象 突然变身成为 Angry 小象，她将对你发出q 次询问，每次询问给出l,r，你需要立刻给出\text{mex}(\{ a_l,a_{l+1}, \cdots, a_r \})的值

第一行两个正整数 $n,q$。

第二行共 $n$ 个数，保证为 $0\sim n-1$ 的排列。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问。

共 $q$ 行，每行一个整数，表示询问的答案。

对于 60\% 的数据：n,q \leq 10^3

对于 100\% 的数据：n,q \leq 10^5,1\leq l \leq r \leq n