Nene дала вам массив целых чисел $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 \le a_i \le 10^7$) — массив $a$.

Выходные данные

В первой строке выведите два целых числа $s$ и $m$ ($0 \le m \le 5\cdot 10^5$) — максимальную сумму элементов массива $a$ и количество операций в вашем решении.

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

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

Примеры

Пример 1

2
0 1

Выходные данные 1

4 1
1 2

Пример 2

3
1 3 9

Выходные данные 2

13 0

Пример 3

4
1 100 2 1

Выходные данные 3

105 2
3 3
3 4

Пример 4

1
0

Выходные данные 4

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