In addition to school and a mathematical club, Vasya goes to a chess club. But playing chess on a regular board is 8 × 8 does not seem very interesting to him. Recently, he came up with his own version of chess, in which the game takes place on a board that has a different shape. Vasya's board consists of n columns, the i-th of which contains ai cells. The bottom cells of all columns form one horizontal row, and the lengths of the columns are ordered from left to right in non-increasing order. The figure below shows an example of a board with three columns containing 5, 2 and 1 cells, respectively.
Today, at the chess club, the lesson was devoted to rook endings, and Vasya was interested in the question: how to arrange the minimum number of rooks on his board so that at least one rook captures each square of the field. The rook beats those cells that are located with it on the same vertical or the same horizontal. Help Vasya arrange the minimum number of rooks on his board in the required way.
Input data format
The first line of the input file contains an integer n — number of board columns
(1 ≤ n ≤ 1000). The next line contains n numbers a1, a2, . . . , an — number of cells in columns
(1 ≤ ai ≤ 1000, a1 ≥ a2 ≥ . . . ≥ an).
Output format
In the first line print the number k — the minimum number of rooks that can be placed on the board so that each cell on the board is attacked by at least one rook. The next k lines should contain descriptions of the rook positions, one per line. The position of the rook is given by two numbers: the number of the column in which the rook stands and the number of the cell in the column. Columns are numbered starting from 1, from left to right, cells in columns are numbered from bottom to top, also starting from 1.
If there are several suitable arrangements, you can display any one.