Railways in Berland
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] trains that will go to other cities. Therefore, the number of railways leaving the i - th city must be equal to d[i]. Fortunately, it turned out that d[1] + d[2] + ... + 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 ≤ n ≤ 200 000). The next line contains n integers d[1], d[2], ..., d[n] (1 ≤ d[i] < n). The number of cities connected to the i - th railroad must be the same as d[i] for any i city. It is guaranteed that d[1] + d[2] + ... + d[n] = 2n - 2.
Output
Print n - 1 lines - the description of the railways in the optimal plan. Each line must contain two integers s[i] and f[i] - the numbers of cities that need to be connected by an ironexpensive. The conditions 1 ≤ s[i], f[i] ≤ n, s[i] ≠ 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] 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.
Example
In the first test case, the answer is this plan:
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).
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.