【bzoj3585】mex

2014年5月18日3,2450

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

1
2
3
0
3

HINT

数据规模和约定
对于100%的数据:
1<=n,m<=200000
0<=ai<=109
1<=l<=r<=n

对于30%的数据:

1<=n,m<=1000

Source

此题为bzoj3339的升级版。。

区别就在于此题需要离散化

然后就没了。。。