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:=x, a_{l+1}:=x, \ldots, a_r:=x$。

这里，一个整数集合 $\{c_1, c_2, \ldots, c_k\}$ 的 $\operatorname{MEX}$ 定义为不在集合 $c$ 中出现的最小非负整数 $m$。

你的目标是最大化数组 $a$ 的元素之和。求出最大和并构造一个达到该和的操作序列。请注意，你不需要最小化操作次数，只需在你的解决方案中使用不超过 $5\cdot 10^5$ 次操作即可。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 18$）—— 数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\leq a_i \leq 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$ 次操作的参数。

可以证明，总能在不超过 $5 \cdot 10^5$ 次操作内获得数组 $a$ 的最大元素和。

样例

输入 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]$。可以证明无法获得更大的数组 $a$ 元素和，因此答案为 $4$。

在第二个样例中，初始元素和为 $13$，可以证明这是最大的和。

在第三个样例中，数组 $a$ 的变化如下：

• 在第一次操作（$l=3$，$r=3$）后，数组 $a$ 变为 $[1,100,0,1]$；
• 在第二次操作（$l=3$，$r=4$）后，数组 $a$ 变为 $[1,100,2,2]$。

可以证明无法获得更大的数组 $a$ 元素和，因此答案为 $105$。