D. Нина и MEX
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нина дала вам массив целых чисел $$$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$$$.

Здесь $$$\operatorname{MEX}$$$ множества целых чисел $$$\{c_1, c_2, \ldots, c_k\}$$$ определяется как наименьшее неотрицательное целое число $$$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$$$ и количество операций в вашем решении.

В $$$i$$$-й из следующих $$$m$$$ строк выведите два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$), представляющие параметры $$$i$$$-й операции.

Можно показать, что максимальная сумма элементов массива $$$a$$$ всегда может быть получена не более чем за $$$5 \cdot 10^5$$$ операций.

Примеры
Входные данные
2
0 1
Выходные данные
4 1
1 2
Входные данные
3
1 3 9
Выходные данные
13 0
Входные данные
4
1 100 2 1
Выходные данные
105 2
3 3
3 4
Входные данные
1
0
Выходные данные
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$$$.