D. Nene and the Mex Operator
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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.

Examples
Input
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$$$.