Ferume 问我是否能比 $O(n\sqrt{n} \log n)$ 更快地解决这个问题。结果我真的可以！感谢他创造了这道题，没有让它沦为一道无聊的题目。

令 $S$ 为一个包含非负整数的多重集。你可以对 $S$ 进行任意次数（可能为零）的以下操作：选择一个 $x$，使得 $S$ 中至少有两个 $x$，删除其中一个 $x$，并插入一个 $(x - 1)$ 或 $(x + 1)$（仅当 $(x - 1)$ 为非负整数时才能插入）。令 $F(S)$ 为通过这些操作所能达到的最大 mex 值。其中 $\text{mex}(S)$ 是指不在 $S$ 中的最小非负整数。

给定一个长度为 $n$ 的数组 $a$ 和 $q$ 个查询 $[l; r]$。对于每个查询，求 $F(\{a_l, a_{l+1}, \dots, a_r\})$。

输入格式

第一行包含两个整数 $n, q$ ($1 \le n, q \le 5 \cdot 10^5$)，表示数组的大小和查询的数量。 第二行包含数组 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 5 \cdot 10^5$)。 接下来的 $q$ 行，每行包含两个整数 $l_i, r_i$ ($1 \le l_i \le r_i \le n$)，表示第 $i$ 个查询。

输出格式

按输入顺序输出每个查询的答案，每行一个。

样例

样例输入 1

3 3
0 0 2
1 3
2 3
3 3

样例输出 1

3
1
0

样例输入 2

3 2
1 2 2
1 2
1 3

样例输出 2

0
3