Minimum Diameter Tree Construction

Given a positive integer n and a sequence of n positive integers d₁, d₂, ..., d_n representing the degree of each vertex, construct a tree T' on n nodes with the given degree sequence such that the diameter \(\operatorname{diam}(T')\) is minimized. The diameter of a tree is defined as the maximum distance between any two nodes. It is guaranteed that at least one valid tree exists. If there are several valid answers, output any one of them.

Note: In the output, first print the minimized diameter on a single line. Then print n-1 lines, each containing two integers that represent an edge of the tree.

The mathematical formulas must be rendered in LaTeX format. For example, the diameter is expressed as \(\operatorname{diam}(T')\) and the degree of node i is \(d_i\).

inputFormat

The input consists of two lines. The first line contains a single integer n (n ≥ 2), the number of nodes in the tree. The second line contains n space-separated positive integers d₁, d₂, ..., d_n, which represent the specified degree for each node. It is guaranteed that \(\sum_{i=1}^n d_i = 2(n-1)\), so that a tree with the given degree sequence exists.

outputFormat

Output the minimized diameter on the first line. Then output n-1 lines, each line containing two space-separated integers representing an edge in the constructed tree. The tree must satisfy the given degree sequence and its diameter must be minimized among all possible trees with that degree sequence.

sample

2
1 1

1
1 2