← 返回题目列表

Codeforces · 1956/D

D. 内内和墨西哥接线员

中文机器翻译题面 查看原题

Nene 给了你一个整数数组 $$$a_1, a_2, \ldots, a_n$$$ 长度为 $$$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:=x, a_{l+1}:=x, \ldots, a_r:=x$$$。

这里,整数集合 $$$\{c_1, c_2, \ldots, c_k\}$$$ 中的 $$$\operatorname{MEX}$$$ 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$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$$$行的第$$$i$$$行中,输出两个整数$$$l$$$和$$$r$$$ ($$$1 \le l \le r \le n$$$),代表第$$$i$$$操作的参数。

可以证明,数组 $$$a$$$ 的最大元素总和总是可以在不超过 $$$5 \cdot 10^5$$$ 操作中获得。

示例

输入 #1

2
0 1

输出 #1

4 1
1 2

输入 #2

3
1 3 9

输出 #2

13 0

输入 #3

4
1 100 2 1

输出 #3

105 2
3 3
3 4

输入#4

1
0

输出#4

1 1
1 1

注意

在第一个示例中,在 $$$l=1$$$ 和 $$$r=2$$$ 运算之后,数组 $$$a$$$ 变为等于 $$$[2,2]$$$。可以证明$$$a$$$的元素之和是不可能达到的,所以答案是$$$4$$$。

在第二个示例中,元素的初始总和为 $$$13$$$,可以证明它是最大的。

在第三个示例中,数组 $$$a$$$ 更改如下:

- 在第一次操作($$$l=3$$$, $$$r=3$$$)之后,数组 $$$a$$$ 变得等于 $$$[1,100,0,1]$$$;
- 第二次操作($$$l=3$$$, $$$r=4$$$)之后,数组 $$$a$$$ 变得等于 $$$[1,100,2,2]$$$。

可以证明$$$a$$$的元素之和是不可能达到的,所以答案是$$$105$$$。