Nene는 길이 $n$인 정수 배열 $a_1, a_2, \ldots, a_n$을 주었습니다.

당신은 다음 연산을 최대 $5\cdot 10^5$번(0번도 가능) 수행할 수 있습니다:

• $1 \le l \le r \le n$인 두 정수 $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}$는 집합 $c$에 포함되지 않는 가장 작은 음이 아닌 정수 $m$으로 정의됩니다.

당신의 목표는 배열 $a$의 원소 합을 최대화하는 것입니다. 최대 합을 구하고, 이 합을 달성하는 연산 순서를 구성하십시오. 연산 횟수를 최소화할 필요는 없으며, 솔루션에서 $5\cdot 10^5$번 이하의 연산만 사용하면 됩니다.

입력

첫 번째 줄에는 배열 $a$의 길이인 정수 $n$ ($1 \le n \le 18$)이 주어집니다.

두 번째 줄에는 $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$)을 출력하십시오.

이어지는 $m$개의 줄 각각에는 $i$번째 연산의 매개변수를 나타내는 두 정수 $l$과 $r$ ($1 \le l \le r \le n$)을 출력하십시오.

배열 $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]$가 됩니다. $a$의 원소 합을 이보다 크게 만드는 것은 불가능하므로 정답은 $4$입니다.

두 번째 예제에서 초기 원소 합은 $13$이며, 이것이 최댓값임이 증명 가능합니다.

세 번째 예제에서 배열 $a$는 다음과 같이 변합니다:

• 첫 번째 연산($l=3, r=3$) 후, 배열 $a$는 $[1,100,0,1]$이 됩니다.
• 두 번째 연산($l=3, r=4$) 후, 배열 $a$는 $[1,100,2,2]$가 됩니다.

$a$의 원소 합을 이보다 크게 만드는 것은 불가능하므로 정답은 $105$입니다.