Nene dała ci tablicę liczb całkowitych $a_1, a_2, \ldots, a_n$ o długości $n$.

Możesz wykonać poniższą operację nie więcej niż $5\cdot 10^5$ razy (możliwe jest wykonanie zera operacji):

• Wybierz dwie liczby całkowite $l$ oraz $r$ takie, że $1 \le l \le r \le n$, oblicz $x$ jako $\operatorname{MEX}(\{a_l, a_{l+1}, \ldots, a_r\})$, a następnie jednocześnie ustaw $a_l:=x, a_{l+1}:=x, \ldots, a_r:=x$.

Tutaj $\operatorname{MEX}$ zbioru liczb całkowitych $\{c_1, c_2, \ldots, c_k\}$ jest zdefiniowany jako najmniejsza nieujemna liczba całkowita $m$, która nie występuje w zbiorze $c$.

Twoim celem jest zmaksymalizowanie sumy elementów tablicy $a$. Znajdź maksymalną sumę i skonstruuj ciąg operacji, który pozwala ją osiągnąć. Zauważ, że nie musisz minimalizować liczby operacji w tym ciągu, powinieneś jedynie użyć nie więcej niż $5\cdot 10^5$ operacji w swoim rozwiązaniu.

Wejście

Pierwsza linia zawiera liczbę całkowitą $n$ ($1 \le n \le 18$) — długość tablicy $a$.

Druga linia zawiera $n$ liczb całkowitych $a_1,a_2,\ldots,a_n$ ($0\leq a_i \leq 10^7$) — tablicę $a$.

Wyjście

W pierwszej linii wypisz dwie liczby całkowite $s$ oraz $m$ ($0\le m\le 5\cdot 10^5$) — maksymalną sumę elementów tablicy $a$ oraz liczbę operacji w twoim rozwiązaniu.

W każdej z kolejnych $m$ linii wypisz dwie liczby całkowite $l$ oraz $r$ ($1 \le l \le r \le n$), reprezentujące parametry $i$-tej operacji.

Można wykazać, że maksymalną sumę elementów tablicy $a$ zawsze można uzyskać w nie więcej niż $5 \cdot 10^5$ operacjach.

Przykład

Przykład 1

2
0 1

Wyjście 1

4 1
1 2

Przykład 2

3
1 3 9

Wyjście 2

13 0

Przykład 3

4
1 100 2 1

Wyjście 3

105 2
3 3
3 4

Przykład 4

1
0

Wyjście 4

1 1
1 1

Uwagi

W pierwszym przykładzie, po operacji z $l=1$ oraz $r=2$, tablica $a$ staje się równa $[2,2]$. Można wykazać, że nie da się osiągnąć większej sumy elementów $a$, więc odpowiedzią jest $4$.

W drugim przykładzie początkowa suma elementów wynosi $13$, co, jak można wykazać, jest wartością największą.

W trzecim przykładzie tablica $a$ zmienia się w następujący sposób:

• po pierwszej operacji ($l=3$, $r=3$), tablica $a$ staje się równa $[1,100,0,1]$;
• po drugiej operacji ($l=3$, $r=4$), tablica $a$ staje się równa $[1,100,2,2]$.

Można wykazać, że nie da się osiągnąć większej sumy elementów $a$, więc odpowiedzią jest $105$.