题目描述

档案馆里有一批编号记录。对任意一个由非负整数构成的多重集合 S，管理员可以重复执行以下操作任意多次，也可以一次都不执行：

选择一个整数 x，要求 S 中至少有两个 x。删除其中一个 x，并插入一个 x - 1 或 x + 1。只有当 x - 1 >= 0 时，才允许插入 x - 1。

记 mex(S) 为 S 中没有出现过的最小非负整数。定义 F(S) 为经过上述操作后，能够得到的最大 mex。

现在给定长度为 n 的数组 a，以及 q 个区间询问 [l, r]。对每个询问，你需要计算：

F({a_l, a_{l+1}, ..., a_r})

其中花括号表示这个区间内元素构成的多重集合。

输入格式

第一行包含两个整数 n, q，分别表示数组长度和询问数量。

第二行包含 n 个整数 a_1, a_2, ..., a_n。

接下来 q 行，每行包含两个整数 l_i, r_i，表示一个询问区间。

输出格式

对每个询问，按输入顺序输出一行一个整数，表示对应的答案。

数据范围

• 1 <= n, q <= 500000
• 0 <= a_i <= 500000
• 1 <= l_i <= r_i <= n

样例

样例 1

3 3
0 0 2
1 3
2 3
3 3

3
1
0

样例 2

3 2
1 2 2
1 2
1 3

0
3