Nene cho bạn một mảng các số nguyên $a_1, a_2, \ldots, a_n$ có độ dài $n$.

Bạn có thể thực hiện thao tác sau không quá $5\cdot 10^5$ lần (có thể không thực hiện lần nào):

• Chọn hai số nguyên $l$ và $r$ sao cho $1 \le l \le r \le n$, tính $x = \operatorname{MEX}(\{a_l, a_{l+1}, \ldots, a_r\})$, và đồng thời gán $a_l:=x, a_{l+1}:=x, \ldots, a_r:=x$.

Ở đây, $\operatorname{MEX}$ của một tập hợp các số nguyên $\{c_1, c_2, \ldots, c_k\}$ được định nghĩa là số nguyên không âm nhỏ nhất $m$ không xuất hiện trong tập hợp $c$.

Mục tiêu của bạn là tối đa hóa tổng các phần tử của mảng $a$. Hãy tìm tổng lớn nhất và xây dựng một chuỗi các thao tác để đạt được tổng này. Lưu ý rằng bạn không cần phải tối thiểu hóa số lượng thao tác, bạn chỉ cần đảm bảo sử dụng không quá $5\cdot 10^5$ thao tác trong lời giải của mình.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 18$) — độ dài của mảng $a$.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($0\leq a_i \leq 10^7$) — mảng $a$.

Dữ liệu ra

Ở dòng đầu tiên, in ra hai số nguyên $s$ và $m$ ($0\le m\le 5\cdot 10^5$) — tổng lớn nhất của các phần tử trong mảng $a$ và số lượng thao tác trong lời giải của bạn.

Trong $m$ dòng tiếp theo, mỗi dòng in ra hai số nguyên $l$ và $r$ ($1 \le l \le r \le n$), biểu thị các tham số của thao tác thứ $i$.

Có thể chứng minh rằng tổng lớn nhất của các phần tử trong mảng $a$ luôn có thể đạt được trong không quá $5 \cdot 10^5$ thao tác.

Ví dụ

Ví dụ 1

2
0 1

Kết quả 1

4 1
1 2

Ví dụ 2

3
1 3 9

Kết quả 2

13 0

Ví dụ 3

4
1 100 2 1

Kết quả 3

105 2
3 3
3 4

Ví dụ 4

1
0

Kết quả 4

1 1
1 1

Ghi chú

Trong ví dụ đầu tiên, sau thao tác với $l=1$ và $r=2$, mảng $a$ trở thành $[2,2]$. Có thể chứng minh rằng không thể đạt được tổng các phần tử của $a$ lớn hơn, vì vậy đáp án là $4$.

Trong ví dụ thứ hai, tổng ban đầu của các phần tử là $13$, đây là tổng lớn nhất có thể đạt được.

Trong ví dụ thứ ba, mảng $a$ thay đổi như sau:

• sau thao tác đầu tiên ($l=3$, $r=3$), mảng $a$ trở thành $[1,100,0,1]$;
• sau thao tác thứ hai ($l=3$, $r=4$), mảng $a$ trở thành $[1,100,2,2]$.

Có thể chứng minh rằng không thể đạt được tổng các phần tử của $a$ lớn hơn, vì vậy đáp án là $105$.