CF1956D.Nene and the Mex Operator

Nene 给了你一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$。

你可以进行如下操作，最多不超过 $5\cdot 10^5$ 次（也可以一次都不做）：

• 选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le n$，计算 $x = \operatorname{MEX}(\{a_l, a_{l+1}, \ldots, a_r\})$，然后同时将 $a_l, a_{l+1}, \ldots, a_r$ 全部赋值为 $x$。

这里，集合 $\{c_1, c_2, \ldots, c_k\}$ 的 $\operatorname{MEX}$ 定义为集合中没有出现的最小非负整数 $m$。

你的目标是最大化数组 $a$ 所有元素的和。请你求出最大和，并构造一组操作序列使得可以达到这个和。注意，你不需要最小化操作次数，只需保证操作次数不超过 $5\cdot 10^5$ 即可。

第一行包含一个整数 $n$（$1 \le n \le 18$），表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\leq a_i \leq 10^7$），表示数组 $a$。

第一行输出两个整数 $s$ 和 $m$（$0\le m\le 5\cdot 10^5$），分别表示数组 $a$ 的最大元素和以及你所用的操作次数。

接下来的 $m$ 行，每行输出两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示第 $i$ 次操作的参数。

可以证明，数组 $a$ 的最大元素和总能在不超过 $5 \cdot 10^5$ 次操作内实现。

在第一个样例中，经过 $l=1$ 且 $r=2$ 的操作后，数组 $a$ 变为 $[2,2]$。可以证明无法得到更大的数组元素和，所以答案为 $4$。

在第二个样例中，初始元素和为 $13$，可以证明这已经是最大的。

在第三个样例中，数组 $a$ 的变化如下：

• 第一次操作（$l=3$，$r=3$）后，数组 $a$ 变为 $[1,100,0,1]$；
• 第二次操作（$l=3$，$r=4$）后，数组 $a$ 变为 $[1,100,2,2]$。

可以证明无法得到更大的数组元素和，所以答案为 $105$。

由 ChatGPT 4.1 翻译