序列（mex）
题目描述
设 S 为一个可重数集，满足所有元素均为非负整数。你可以对 S 进行若干次（可以为 0 次）如下操 作：选择一个非负整数 x 满足 x 至少在 S 中出现了 2 次，在 S 中删除一个 x，并将 (x − 1) 或 (x + 1) 插入 S。如果你选择插入 (x − 1)，你必须保证 (x − 1) 非负。记 F(S) 为通过对 S 进行若 干次如上操作能得到的 mex(S) 的最大值。其中 mex(S) 表示最小的不属于 S 的非负整数。 给定一个长度为 n 的序列 a1…n。有 q 次询问，每次给出 l, r (1 ≤ l ≤ r ≤ n)。对于每一个询问，你 需要回答 F({al , al+1 , … , ar })。
输入格式
第一行两个整数 n ，q。 第二行 n 个整数 a1 , a2 , … , an。 接下来 q 行，每行两个整数 l, r，表示一次询问。
输出格式
共 q 行，每行一个整数，表示询问的答案。
样例
样例 1 输入
4 3 2 0 0 1 2 3 1 3
样例 1 输出
2 3 2
样例 2
见下发文件 ex_mex2.in 和 ex_mex2.ans。
样例 3
见下发文件 ex_mex3.in 和 ex_mex3.ans。
样例 4
见下发文件 ex_mex4.in 和 ex_mex4.ans。
提示
数据范围
子任务编号
分值 n ≤ q ≤ 特殊性质 1 10 1000 1000 无 2 10 5000 5000 无 3 10 105 500 无 4 10 105 105 无 5 10 2 × 105 2 × 105 无 6 10 5 × 105 3 × 105 ai 互不相同 7 10 5 × 105 5 × 105 l = 1 8 10 3 × 105 3 × 105 无 9 10 5 × 105 3 × 105 无
子任务编号 分值 n ≤ q ≤ 特殊性质 10 10 5 × 105 5 × 105 无 对于所有数据，保证 ai ≤ 109， 1 ≤ l ≤ r ≤ n。