Nene 与 MEX 操作

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的非负整数数组 $a$。

你至多可以执行 $5\times10^5$ 次以下操作：选择 $1\le l\le r\le n$，令

然后把 $a_l,a_{l+1},\ldots,a_r$ 同时赋值为 $x$。其中，集合的 $\operatorname{MEX}$ 是没有出现在集合中的最小非负整数。

请最大化最终数组的元素和，并构造任意一组达到最大值的合法操作。你不需要最小化操作次数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

第一行输出两个整数 $s$ 和 $m$，分别表示能达到的最大元素和与操作次数，其中 $0\le m\le5\times10^5$。

接下来 $m$ 行，每行输出两个整数 $l,r$，表示依次执行的一次操作。

只要操作合法并使最终数组元素和等于最大值，任意方案均可通过。

样例输入 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

数据范围

对所有数据，$1\le n\le18$，$0\le a_i\le10^7$。