write a go solution for Description:
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*10^5 times (possibly zero):

- Choose two integers l and r such that 1<=l<=r<=n, compute x as operatornameMEX(a_l,a_l+1,ldots,a_r), and simultaneously set a_l:=x,a_l+1:=x,ldots,a_r:=x.

Here, operatornameMEX 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*10^5 operations in your solution.

Input Format:
The first line contains an integer n (1<=n<=18) — the length of the array a.

The second line contains n integers a_1,a_2,ldots,a_n (0<=qa_i<=q10^7) — the array a.

Output Format:
In the first line, output two integers s and m (0<=m<=5*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<=l<=r<=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*10^5 operations.

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.. Output only the code with no comments, explanation, or additional text.