311252: CF1956D. Nene and the Mex Operator

D. Nene and the Mex Operatortime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Nene gave you an array of integers $a_1, a_2, \ldots, a_n$ of length $n$.

You can perform the following operation no more than $5\cdot 10^5$ times (possibly zero):

• Choose two integers $l$ and $r$ such that $1 \le l \le r \le n$, compute $x$ as $\operatorname{MEX}(\{a_l, a_{l+1}, \ldots, a_r\})$, and simultaneously set $a_l:=x, a_{l+1}:=x, \ldots, a_r:=x$.

Here, $\operatorname{MEX}$ of a set of integers $\{c_1, c_2, \ldots, c_k\}$ is defined as the smallest non-negative integer $m$ which does not occur in the set $c$.

Your goal is to maximize the sum of the elements of the array $a$. Find the maximum sum and construct a sequence of operations that achieves this sum. Note that you don't need to minimize the number of operations in this sequence, you only should use no more than $5\cdot 10^5$ operations in your solution.

Input

The first line contains an integer $n$ ($1 \le n \le 18$) — the length of the array $a$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\leq a_i \leq 10^7$) — the array $a$.

Output

In the first line, output two integers $s$ and $m$ ($0\le m\le 5\cdot 10^5$) — the maximum sum of elements of the array $a$ and the number of operations in your solution.

In the $i$-th of the following $m$ lines, output two integers $l$ and $r$ ($1 \le l \le r \le n$), representing the parameters of the $i$-th operation.

It can be shown that the maximum sum of elements of the array $a$ can always be obtained in no more than $5 \cdot 10^5$ operations.

ExamplesInput

2
0 1

Output

4 1
1 2

Input

3
1 3 9

Output

13 0

Input

4
1 100 2 1

Output

105 2
3 3
3 4

Input

1
0

Output

1 1
1 1

Note

In the first example, after the operation with $l=1$ and $r=2$ the array $a$ becomes equal to $[2,2]$. It can be shown that it is impossible to achieve a larger sum of the elements of $a$, so the answer is $4$.

In the second example, the initial sum of elements is $13$ which can be shown to be the largest.

In the third example, the array $a$ changes as follows:

• after the first operation ($l=3$, $r=3$), the array $a$ becomes equal to $[1,100,0,1]$;
• after the second operation ($l=3$, $r=4$), the array $a$ becomes equal to $[1,100,2,2]$.

It can be shown that it is impossible to achieve a larger sum of the elements of $a$, so the answer is $105$.

**题目大意：**
Nene给你一个由整数组成的数组$a_1, a_2, \ldots, a_n$，长度为$n$。你可以执行以下操作，但不超过$5\cdot 10^5$次（可能为零次）：
- 选择两个整数$l$和$r$，使得$1 \le l \le r \le n$，计算$x$作为集合$\{a_l, a_{l+1}, \ldots, a_r\}$的$\operatorname{MEX}$，并同时设置$a_l:=x, a_{l+1}:=x, \ldots, a_r:=x$。
这里，集合$\{c_1, c_2, \ldots, c_k\}$的$\operatorname{MEX}$定义为最小的非负整数$m$，它不在集合$c$中出现。

你的目标是最大化数组$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$次操作中得到。**题目大意：** Nene给你一个由整数组成的数组$a_1, a_2, \ldots, a_n$，长度为$n$。你可以执行以下操作，但不超过$5\cdot 10^5$次（可能为零次）： - 选择两个整数$l$和$r$，使得$1 \le l \le r \le n$，计算$x$作为集合$\{a_l, a_{l+1}, \ldots, a_r\}$的$\operatorname{MEX}$，并同时设置$a_l:=x, a_{l+1}:=x, \ldots, a_r:=x$。 这里，集合$\{c_1, c_2, \ldots, c_k\}$的$\operatorname{MEX}$定义为最小的非负整数$m$，它不在集合$c$中出现。 你的目标是最大化数组$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$次操作中得到。