Railways in Berland#8712

Railways in Berland

1 second

128 megabytes

Hard

The government of Berland decided to build a high-speed rail system in the country. Berland has $n$ cities numbered with positive integers from $1$ to $n$ . It is planned to connect some pairs of cities with high speed railways. Each of the roads will be able to move in both directions between the cities that it connects.

High speed railways are the future, so it is necessary that, using railways, one can get from any city to any other. In order to save money, it was decided to build the minimum number of roads necessary to fulfill this condition.

The government of the $i$ -th city is ready to serve exactly $d_{i}$ d_i trains that will go to other cities. Therefore, the number of railways leaving the $i$ -th city must be equal to $d_{i}$ d_i. Fortunately, it turned out that $d_{1} + d_{2} + \dots + d_{n} = 2 n - 2$ d_1 + d_2 + \ldots + d_n = 2n - 2.

The government wants residents to be able to move between cities with as few transfers as possible. It is necessary to make such a plan of the railway system so that the maximum number of changes that must be made to get from one city to another is as small as possible.

Input

The first line contains an integer $n$ - the number of cities in Berland ( $2 \leq n \leq 200000$ 2 \leq n \leq 200\,000). The next line contains $n$ integers $d_{1}, d_{2}, \dots, d_{n}$ d_1, d_2, \ldots, d_n ( $1 \leq d_{i} < n$ 1 \leq d_i < n). The number of cities connected to the $i$ -th city by railroad must be the same as $d_{i}$ d_i for any city $i$ . It is guaranteed that $d_{1} + d_{2} + \dots + d_{n} = 2 n - 2$ d_1 + d_2 + \ldots + d_n = 2n - 2.

Output

Print $n - 1$ n - 1 lines - the description of the railways in the optimal plan. Each line must contain two integers $s_{i}$ s_i and $f_{i}$ f_i - the numbers of cities that need to be connected by a railway. The conditions $1 \leq s_{i}, f_{i} \leq n$ 1 \leq s_i, f_i \leq n, $s_{i} \neq = f_{i}$ s_i \neq f_i must be satisfied.

The number of cities connected to the $i$ -th city by the railroad must be the same as $d_{i}$ d_i for any city $i$ . The maximum number of transfers required to get from one city to another should be as small as possible. If there are several possible optimal plans for the construction of railways, you can print any of them. It is guaranteed that there is a plan that meets all the conditions.

Examples

Example 1

Example 2

Note

In the first test case, the answer is this plan:

![prb8712.gif](https://static.e-olymp.com/content/0a/0ab1e34cd80b6d00d471c9c599a0cf46595fae07.gif)

You can see that from any city you can get to any other using the railways. Also, each city is connected by rail to the required number of cities. For example, city $1$ is connected to three cities: $2$ , $4$ and $6$ ( $d_{1} = 3$ d_1 = 3).

The maximum number of changes required to get from one city to another is reached, for example, for cities $3$ and $5$ , for this you need to use $3$ transfers. First you need to get from the city $3$ to the city $2$ , then from the city $2$ to the city $1$ , then from the city $1$ to the city $4$ and finally from city $4$ to city $5$ . It is impossible to build a plan in which the maximum number of transfers is less.