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$$$。