希望有羽毛和翅膀 - 知更鸟 / HOYO-MiX / Chevy

题目描述

云浅给了你一个非负整数构成的可重集合 $S$，你可以进行任意次操作，每次你可以从集合中选一个数 $x$，满足 $x$ 在集合中出现至少两次，然后删除 $x$，并插入 $x-1$（此时需保证 $x\ge 1$）或 $x+1$。

你希望最大化 $S$ 中所有元素的 $\text{mex}$。定义上述问题的答案为 $F(S)$。

• 一个集合 $S$ 的 $\text{mex}$ 定义为最小的没有出现过的非负整数，例如 $\text{mex}(\{0,1,3\})=2,\text{mex}(\{1,2\})=0$。

给定一个长为 $n$ 的序列 $a$，有 $q$ 次询问，每次询问给出 $l,r$，你需要输出 $F(\{a_l,a_{l+1},\cdots,a_r\})$ 的值。

输入格式

第一行两个正整数 $n,q$。

接下来一行 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$。

接下来 $q$ 行，每行两个正整数 $l,r$。

输出格式

对于每组询问，输出一行一个正整数表示答案。

样例 $1$ 输入

10 9
3 0 0 0 5 1 1 1 2 1
1 2
8 8
5 7
1 7
2 2
1 5
5 6
4 6
3 10

样例 $1$ 输出

1
0
2
7
1
4
0
2
8

样例 $1$ 解释

以询问 $[1,5]$ 为例：$S=\{0,0,0,3,5\}$，我们进行如下操作：

• 删去一个 $0$，插入一个 $1$，此时 $S=\{0,0,1,3,5\}$。
• 删去一个 $0$，插入一个 $1$，此时 $S=\{0,1,1,3,5\}$。
• 删去一个 $1$，插入一个 $2$，此时 $S=\{0,1,2,3,5\}$。

最终 $S=\{0,1,2,3,5\}$，有 $\text{mex}(S)=4$，为可能的 $\text{mex}(S)$ 的最大值。

注意不能删去 $5$ 然后插入 $4$，因为 $5$ 在 $S$ 中只出现了一次。

测试点约束

对于所有数据，$1\le n,q\le 5\times 10^5,0\le a_i\le 5\times 10^5$。