#3585. mex

题目描述

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

输入格式

第一行n,m。
第二行为n个数。
从第三行开始，每行一个询问l,r。

输出格式

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

样例

样例输入

5 5  

2 1 0 2 1  

3 3  

2 3  

2 4  

1 2  

3 5  

样例输出

1  

2  

3  

0  

3  

数据范围与提示

数据规模和约定

对于100%的数据：

1<=n,m<=200000

0<=ai<=109

1<=l<=r<=n

对于30%的数据：

1<=n,m<=1000