Nene te ha dado un arreglo de enteros $a_1, a_2, \ldots, a_n$ de longitud $n$.

Puedes realizar la siguiente operación no más de $5\cdot 10^5$ veces (posiblemente cero):

• Elige dos enteros $l$ y $r$ tales que $1 \le l \le r \le n$, calcula $x$ como $\operatorname{MEX}(\{a_l, a_{l+1}, \ldots, a_r\})$, y simultáneamente establece $a_l:=x, a_{l+1}:=x, \ldots, a_r:=x$.

Aquí, el $\operatorname{MEX}$ de un conjunto de enteros $\{c_1, c_2, \ldots, c_k\}$ se define como el entero no negativo más pequeño $m$ que no aparece en el conjunto $c$.

Tu objetivo es maximizar la suma de los elementos del arreglo $a$. Encuentra la suma máxima y construye una secuencia de operaciones que logre esta suma. Ten en cuenta que no necesitas minimizar el número de operaciones en esta secuencia, solo debes usar no más de $5\cdot 10^5$ operaciones en tu solución.

Entrada

La primera línea contiene un entero $n$ ($1 \le n \le 18$) — la longitud del arreglo $a$.

La segunda línea contiene $n$ enteros $a_1,a_2,\ldots,a_n$ ($0\leq a_i \leq 10^7$) — el arreglo $a$.

Salida

En la primera línea, imprime dos enteros $s$ y $m$ ($0\le m\le 5\cdot 10^5$) — la suma máxima de los elementos del arreglo $a$ y el número de operaciones en tu solución.

En la $i$-ésima de las siguientes $m$ líneas, imprime dos enteros $l$ y $r$ ($1 \le l \le r \le n$), que representan los parámetros de la $i$-ésima operación.

Se puede demostrar que la suma máxima de los elementos del arreglo $a$ siempre se puede obtener en no más de $5 \cdot 10^5$ operaciones.

Ejemplos

Entrada 1

2
0 1

Salida 1

4 1
1 2

Entrada 2

3
1 3 9

Salida 2

13 0

Entrada 3

4
1 100 2 1

Salida 3

105 2
3 3
3 4

Entrada 4

1
0

Salida 4

1 1
1 1

Nota

En el primer ejemplo, después de la operación con $l=1$ y $r=2$, el arreglo $a$ se convierte en $[2,2]$. Se puede demostrar que es imposible lograr una suma mayor de los elementos de $a$, por lo que la respuesta es $4$.

En el segundo ejemplo, la suma inicial de los elementos es $13$, lo cual se puede demostrar que es la mayor posible.

En el tercer ejemplo, el arreglo $a$ cambia de la siguiente manera:

• después de la primera operación ($l=3$, $r=3$), el arreglo $a$ se convierte en $[1,100,0,1]$;
• después de la segunda operación ($l=3$, $r=4$), el arreglo $a$ se convierte en $[1,100,2,2]$.

Se puede demostrar que es imposible lograr una suma mayor de los elementos de $a$, por lo que la respuesta es $105$.