Home => ProblemSet => mex
Problem2309--mex

2309: mex

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 1
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

有一个长度为n的数组a1,a2,...,an
有m个询问，每次给一个区间[l,r]，询问这个区间内最小没有出现过的自然数

Input

第一行两个整数n,m(1 <=n, m<= 2*105)
接下来一行n个整数a1,a2,...,an(0<=ai<=109)
接下来m行每行两个整数l, r(1 <= l <= r <= n)

Output

对于每个询问每行一个整数表示答案

Sample Input Copy 

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

Sample Output Copy 

1
2
3
0
3

Source/Category

数据结构 线段树 
[ Submit ] [ Status ]