← 返回题目列表

Codeforces · 174/C

C. 范围增量

中文机器翻译题面 查看原题

Polycarpus 是一位业余程序员。现在他正在分析一个朋友的程序。他已经在那里找到了函数 rangeIncrement(l, r),该函数为段 [l, r] 中的所有索引的某个数组 a 的每个元素加 1。换句话说,该函数执行以下操作:

Polycarpus 在一系列函数调用后知道数组 a 的状态。他想要确定导致这种状态的函数调用的最小数量。另外,他想找出这种情况下需要哪些函数调用。保证所需调用次数不超过105。

在调用函数 rangeIncrement(l, r) 之前,所有数组元素都为零。

输入

第一个输入行包含一个整数 n (1 ≤ n ≤ 105) — 数组 a[1...n] 的长度。

在一系列函数调用 rangeIncrement(l, r) 之后,第二行包含其空格分隔的整数元素 a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 105)。

保证数组中至少有一个元素为正。保证答案包含的函数 rangeIncrement(l, r) 调用不超过 105 次。

输出

在第一行打印 t — 从输入数据通向数组的函数 rangeIncrement(l, r) 的最小调用次数。保证这个数字不会超过 105。

然后打印 t 行——函数调用的描述,每行一个。每行应包含两个整数 li, ri (1 ≤ li ≤ ri ≤ n) — 第 i 次调用 rangeIncrement(l, r) 的参数。可以按任何顺序进行调用。

如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

6
1 2 1 1 4 1

输出 #1

5
2 2
5 5
5 5
5 5
1 6

输入 #2

5
1 0 1 0 1

输出 #2

3
1 1
3 3
5 5

注意

第一个示例需要调用整个数组,以及四个附加调用:

- 1 表示段 [2,2](即数组的第二个元素),
- 三个表示段 [5,5](即数组的第五个元素)。