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}$ 定义为集合 $c$ 中未出现的最小非负整数 $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$。