Berland Railroads

The Berland government has decided to build a system of high speed railroads in the country. There are $n$ cities in Berland, numbered from $1$ to $n$. Some pairs of cities will be connected by a high speed railroad. Travelers can move by train in both directions along each railroad.

High speed trains are the future of transport, so the plan must allow travel from any city to any other city by rail. To save money, the government builds the fewest railroads that satisfy this condition.

The government of city $i$ wants to support exactly $d_i$ trains. That is, exactly $d_i$ railroads must connect city $i$ to other cities. It is known that $d_1 + d_2 + \ldots + d_n = 2n - 2$.

The government wants people to change trains as few times as possible. Build the plan so that the maximum number of changes needed to travel from one city to another is as small as possible.

The first line contains an integer $n$, the number of cities ($2 \leq n \leq 200000$). The next line contains $n$ integers $d_1, d_2, \ldots, d_n$ ($1 \leq d_i < n$). City $i$ must be connected to exactly $d_i$ other cities. It is guaranteed that $d_1 + d_2 + \ldots + d_n = 2n - 2$.

Print $n-1$ lines describing the railroads in the optimal plan. Each line contains two integers $s_i$ and $f_i$, the cities to connect ($1 \leq s_i, f_i \leq n$, $s_i \neq f_i$). The number of railroads at city $i$ must equal $d_i$ for every $i$. The maximum number of changes needed to travel between any two cities must be as small as possible. If several plans are optimal, print any of them. It is guaranteed that at least one valid plan exists.

The optimal answer for the first sample is shown below.

City 1 is connected to three cities: 2, 4, and 6 ($d_1 = 3$). The maximum number of changes is 3, for cities 3 and 5. Travel from city 3 to city 2, then from city 2 to city 1, then from city 1 to city 4, and finally from city 4 to city 5. No plan requires fewer changes for every pair of cities.