Nene vous donne un tableau d'entiers $a_1, a_2, \ldots, a_n$ de longueur $n$.

Vous pouvez effectuer l'opération suivante au plus $5\cdot 10^5$ fois (éventuellement zéro) :

• Choisir deux entiers $l$ et $r$ tels que $1 \le l \le r \le n$, calculer $x = \operatorname{MEX}(\{a_l, a_{l+1}, \ldots, a_r\})$, et définir simultanément $a_l:=x, a_{l+1}:=x, \ldots, a_r:=x$.

Ici, le $\operatorname{MEX}$ d'un ensemble d'entiers $\{c_1, c_2, \ldots, c_k\}$ est défini comme le plus petit entier non négatif $m$ qui n'apparaît pas dans l'ensemble $c$.

Votre objectif est de maximiser la somme des éléments du tableau $a$. Trouvez la somme maximale et construisez une séquence d'opérations qui permet d'atteindre cette somme. Notez qu'il n'est pas nécessaire de minimiser le nombre d'opérations dans cette séquence, vous devez simplement utiliser au plus $5\cdot 10^5$ opérations dans votre solution.

Entrée

La première ligne contient un entier $n$ ($1 \le n \le 18$) — la longueur du tableau $a$.

La deuxième ligne contient $n$ entiers $a_1,a_2,\ldots,a_n$ ($0\leq a_i \leq 10^7$) — le tableau $a$.

Sortie

Sur la première ligne, affichez deux entiers $s$ et $m$ ($0\le m\le 5\cdot 10^5$) — la somme maximale des éléments du tableau $a$ et le nombre d'opérations dans votre solution.

Dans chacune des $m$ lignes suivantes, affichez deux entiers $l$ et $r$ ($1 \le l \le r \le n$), représentant les paramètres de la $i$-ième opération.

Il peut être démontré que la somme maximale des éléments du tableau $a$ peut toujours être obtenue en au plus $5 \cdot 10^5$ opérations.

Exemples

Entrée 1

2
0 1

Sortie 1

4 1
1 2

Entrée 2

3
1 3 9

Sortie 2

13 0

Entrée 3

4
1 100 2 1

Sortie 3

105 2
3 3
3 4

Entrée 4

1
0

Sortie 4

1 1
1 1

Remarque

Dans le premier exemple, après l'opération avec $l=1$ et $r=2$, le tableau $a$ devient égal à $[2,2]$. Il peut être démontré qu'il est impossible d'obtenir une somme plus grande des éléments de $a$, donc la réponse est $4$.

Dans le deuxième exemple, la somme initiale des éléments est $13$, ce qui, comme on peut le démontrer, est la valeur maximale.

Dans le troisième exemple, le tableau $a$ change comme suit :

• après la première opération ($l=3$, $r=3$), le tableau $a$ devient égal à $[1,100,0,1]$ ;
• après la deuxième opération ($l=3$, $r=4$), le tableau $a$ devient égal à $[1,100,2,2]$.

Il peut être démontré qu'il est impossible d'obtenir une somme plus grande des éléments de $a$, donc la réponse est $105$.