题目描述

大笨龙把车票一张挨一张钉在森林车站的失物板上。同一票号可能出现好几次。聪明兔沿着板子巡查，每次只掀开从第 l 张到第 r 张的遮布。

补票机从 0 开始试号，遇到眼前已有的票号就跳过，遇到第一个没出现的票号就停下。每次掀开遮布，它会停在哪个数？询问之间，板上的车票保持原样。

输入格式

第一行是两个正整数 n、m，分别表示车票数和询问数。第二行依次给出 n 个非负整数，表示从左到右的票号。接下来 m 行，每行两个整数 l、r。车票从 1 开始编号，两端都在查看范围内。

输出格式

按询问顺序输出 m 行，每行一个整数，表示该段车票中没有出现的最小非负整数。

样例 1

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

1
2
3
0
3

第三次掀开第 2 至第 4 张车票，能看到 1、0、2，因此补票机停在 3。第四次只能看到 2、1，机器一开始就停在 0。

样例 2

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

1
0
1

整段中虽然有两张 0 号票，1 号仍然空着。单看第 3 张时，只有 0 号票，答案也是 1。

样例 3

输入文件 · 答案文件

样例 4

输入文件 · 答案文件

数据范围

1 ≤ n, m ≤ 200000，0 ≤ 票号 ≤ 200000，1 ≤ l ≤ r ≤ n。

共 20 个独立测试点，每点 5 分。