Nene 給了你一個長度為 $n$ 的整數陣列 $a_1, a_2, \ldots, a_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, a_{l+1}, \ldots, a_r$ 全部設為 $x$。

其中，一個整數集合 $\{c_1, c_2, \ldots, c_k\}$ 的 $\operatorname{MEX}$ 定義為不在該集合中出現的最小非負整數 $m$。

你的目標是使陣列 $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$ 行中，第 $i$ 行輸出兩個整數 $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]$。可以證明無法達到更大的總和，因此答案為 $4$。

在第二個範例中，初始總和為 $13$，可以證明這是最大值。

在第三個範例中，陣列 $a$ 的變化如下：

• 第一次操作 ($l=3, r=3$) 後，陣列 $a$ 變為 $[1,100,0,1]$；
• 第二次操作 ($l=3, r=4$) 後，陣列 $a$ 變為 $[1,100,2,2]$。

可以證明無法達到更大的總和，因此答案為 $105$。