Description

某人区域赛前写不下去代码怎么办？？？出题！！！”早就憋着出这题给你们做了 -_-! “

我们定义一个函数$mex$为序列中未出现的最小非负整数 。

例：

$mex(${1, 2, 3}$) = 0$

$mex(${0, 2, 1, 3}$) = 4$

$mex(${0, 4, 2, 3}$) = 1$

现在，实验室最苦打工人给了你一个由$n$个非负整数组成的序列$a_1, a_2, ..., a_n$。

他会对你进行$q$次询问，每次将会询问区间$[l, r]$中$mex(${ $a_l, ..., a_r$ }$)$的值是多少。

Format

Input

第一行输入两个数$n, q$。$(1 \leq n, q \leq 100000)$

第二行输入$n$个整数$a_i$，用空格分隔。$(0 \leq a_i \leq 10^9)$

接下来$q$行，每行有两个数$l_i, r_i$表示询问的区间。$(1 \leq l_i \leq r_i \leq n)$

Output

对于每一个询问操作，输出一行。该行只有一个数，即$mex(${ $a_l, ..., a_r$ }$)$的值。

Samples

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

1
2
5

Hint