3585 - mex

有一个长度为n的数组{a_1,a_2,...,a_n}。m次询问，每次询问一个区间内最小没有出现过的自然数。

Input

第一行n,m。

第二行为n个数。

从第三行开始，每行一个询问l,r。

Output

一行一个数，表示每个询问的答案。

Examples

Input

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

Output

1
2
3
0
3

Hint

对于100\%的数据：

1<=n,m<=200000,0<=ai<=10^9,1<=l<=r<=n

对于30\%的数据：

1<=n,m<=1000

时间限制 1 秒
内存限制 1024 MB
统计
上一题 下一题