小象得到了一个0 \sim n-1的排列 a，并且得知了一个新的函数 mex。mex(S)的值为整数集合 S 中未出现的最小自然数。
此时 小象 突然变身成为 Angry 小象，她将对你发出q 次询问，每次询问给出l,r，你需要立刻给出\text{mex}(\{ a_l,a_{l+1}, \cdots, a_r \})的值
第一行两个正整数 n,qn,qn,q。
第二行共 nnn 个数，保证为 0∼n−10 \sim n-10∼n−1 的排列。
接下来 qqq 行，每行两个正整数 l,rl,rl,r，表示一次询问。
共 qqq 行，每行一个整数，表示询问的答案。
4 2 3 0 1 2 2 3 1 4
2 4
对于 60\% 的数据：n,q \leq 10^3
对于 100\% 的数据：n,q \leq 10^5,1\leq l \leq r \leq n
| Time Limit | 1 second |
| Memory Limit | 128 MB |