#P14523. [2026年省队模拟联测]序列

    ID: 13740 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 10 上传者: 标签>数据结构树状数组贪心动态规划CF3000线段树平衡树

[2026年省队模拟联测]序列

序列(sequence)

题目描述

有一个长为 nn 的非负整数序列 a1,…,ana_1,\ldots,a_n。

对于一个可重集 bb,定义其权值为执行若干次如下操作后,其 mex⁡\operatorname{mex} 的最大值:

选择一个在该可重集中至少出现两次的元素 xx,将其中一个变为 x−1x-1(执行此操作时 xx 不能为 00)或 x+1x+1。

支持 qq 组询问。每组询问给定 (l,r)(l,r),求出 {al,…,ar}\{a_l,\ldots,a_r\} 的权值。

输入格式

第一行两个整数 nn 和 qq。

接下来一行 nn 个非负整数,第 ii 个表示 aia_i。

接下来 qq 行,每行两个整数 ll 和 rr,表示一组询问。

输出格式

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

样例 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