Nene and the Mex Operator
Contest: Codeforces Round 939 (Div. 2)
Difficulty rating: 2000
Tags: bitmasks, brute force, constructive algorithms, divide and conquer, dp, greedy, implementation, math

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
2
0 1

Example output:
4 1
1 2

Example input:
3
1 3 9

Example output:
13 0

Editorial:
Hint
What is the answer when $$$a_i = 0$$$?
Solution
When $$$a_i =0$$$, the sum can hit $$$n^2$$$ with making $$$a_i = n$$$ at last. Construction:
Here, solve(k) will take about $$$2^k$$$ operations.
Since doing operation $$$[l,r]$$$ will make $$$a_l,\cdots,a_r \le r-l+1$$$, if for all $$$l\le i\le r$$$, $$$a_i$$$ is included in at least one of the operations and $$$a_{l-1},a_{r+1}$$$ are not, the optimal strategy will be setting $$$a_i = r-l+1$$$ for $$$i\in[l,r]$$$ using the construction above.
Finally, we can use DFS or DP to determine whether each element is included in operations.
The number of operations used will not exceed $$$2^n$$$.