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](即数组的第五个元素)。