CF174C.Range Increments

Polycarpus is an amateur programmer. Now he is analyzing a friend's program. He has already found there the function rangeIncrement(l, r), that adds 1 to each element of some array a for all indexes in the segment [l, r]. In other words, this function does the following:

function rangeIncrement(l, r)
for i := l .. r do
a[i] = a[i] + 1

Polycarpus knows the state of the array a after a series of function calls. He wants to determine the minimum number of function calls that lead to such state. In addition, he wants to find what function calls are needed in this case. It is guaranteed that the required number of calls does not exceed 105.

Before calls of function rangeIncrement(l, r) all array elements equal zero.

波利卡普斯是一名业余程序员。目前他正在分析朋友的一段程序。他已经在其中发现了函数 rangeIncrement(l, r)，该函数对数组 $a$ 中下标在区间 $[l,\,r]$ 内的每个元素加 1。换言之，该函数执行如下操作：

function rangeIncrement(l, r)  
 for i := l .. r do  
 a[i] = a[i] + 1  

波利卡普斯已知数组 $a$ 在若干次调用该函数之后的状态。他希望确定得到该状态所需的最少函数调用次数，并进一步找出这些具体的函数调用。题目保证所需的最少调用次数不超过 $10^5$。

在首次调用 rangeIncrement(l, r) 之前，数组所有元素均为 0。

The first input line contains a single integer n (1 ≤ n ≤ 105) — the length of the array a[1... n].

The second line contains its integer space-separated elements, a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 105) after some series of function calls rangeIncrement(l, r).

It is guaranteed that at least one element of the array is positive. It is guaranteed that the answer contains no more than 105 calls of function rangeIncrement(l, r).

第一行输入包含一个整数 $ n $（$ 1 \leq n \leq 10^5 $）——数组 $ a[1...n] $ 的长度。

第二行包含该数组的整数元素，以空格分隔：$ a[1],\ a[2],\ ...,\ a[n] $（$ 0 \leq a[i] \leq 10^5 $），这些元素是经过若干次函数调用 rangeIncrement(l, r) 后得到的结果。

保证数组中至少有一个元素为正数。保证答案中 rangeIncrement(l, r) 函数调用次数不超过 $ 10^5 $ 次。

Print on the first line t — the minimum number of calls of function rangeIncrement(l, r), that lead to the array from the input data. It is guaranteed that this number will turn out not more than 105.

Then print t lines — the descriptions of function calls, one per line. Each line should contain two integers l__i, r__i (1 ≤ l__i ≤ r__i ≤ n) — the arguments of the i-th call rangeIncrement(l, r). Calls can be applied in any order.

If there are multiple solutions, you are allowed to print any of them.

第一行输出 t —— 使得数组变为输入数据所需的函数 rangeIncrement(l, r) 的最少调用次数。保证该数值不超过 $10^5$。

接下来输出 t 行，每行描述一次函数调用。每行应包含两个整数 l__i、r__i（满足 $1 \leq l_i \leq r_i \leq n$），表示第 i 次调用 rangeIncrement(l, r) 的参数。这些调用可以以任意顺序执行。

若存在多种解法，输出任意一种即可。

The first sample requires a call for the entire array, and four additional calls:

• one for the segment [2,2] (i.e. the second element of the array),
• three for the segment [5,5] (i.e. the fifth element of the array).

第一个样例需要对整个数组进行一次调用，以及四次额外的调用：

• 一次针对区间 [2,2]（即数组的第二个元素），
• 三次针对区间 [5,5]（即数组的第五个元素）。