Neneは長さ $n$ の整数配列 $a_1, a_2, \ldots, a_n$ をあなたに与えました。

あなたは以下の操作を $5\cdot 10^5$ 回以下（0回でもよい）行うことができます。

• $1 \le l \le r \le n$ を満たす2つの整数 $l$ と $r$ を選び、$x = \operatorname{MEX}(\{a_l, a_{l+1}, \ldots, a_r\})$ を計算し、同時に $a_l:=x, a_{l+1}:=x, \ldots, a_r:=x$ と置き換える。

ここで、整数の集合 $\{c_1, c_2, \ldots, c_k\}$ の $\operatorname{MEX}$ とは、その集合に含まれない最小の非負整数 $m$ のことである。

あなたの目標は、配列 $a$ の要素の総和を最大化することである。最大となる総和を求め、その総和を達成する操作手順を構築せよ。なお、操作回数を最小化する必要はなく、$5\cdot 10^5$ 回以下の操作で達成すればよい。

入力

1行目に整数 $n$ ($1 \le n \le 18$) が与えられる。これは配列 $a$ の長さである。

2行目に $n$ 個の整数 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^7$) が与えられる。これは配列 $a$ である。

出力

1行目に、配列 $a$ の最大総和 $s$ と、操作回数 $m$ ($0 \le m \le 5\cdot 10^5$) を出力せよ。

続く $m$ 行の各行に、操作のパラメータを表す2つの整数 $l$ と $r$ ($1 \le l \le r \le n$) を出力せよ。

配列 $a$ の最大総和は、常に $5 \cdot 10^5$ 回以下の操作で達成できることが示されている。

入出力例

入出力例 1

2
0 1

4 1
1 2

入出力例 2

3
1 3 9

13 0

入出力例 3

4
1 100 2 1

105 2
3 3
3 4

入出力例 4

1
0

1 1
1 1

注記

最初の例では、$l=1, r=2$ の操作を行うと、配列 $a$ は $[2, 2]$ となる。これより大きい総和を得ることは不可能であるため、答えは $4$ となる。

2番目の例では、初期の総和は $13$ であり、これが最大であることが示せる。

3番目の例では、配列 $a$ は以下のように変化する。

• 1回目の操作 ($l=3, r=3$) 後、配列 $a$ は $[1, 100, 0, 1]$ となる。
• 2回目の操作 ($l=3, r=4$) 後、配列 $a$ は $[1, 100, 2, 2]$ となる。

これより大きい総和を得ることは不可能であるため、答えは $105$ となる。