There are n towns with their own airports in the country X. We know the maximal
capacities of the airports - the airport in the town Mi can
have at most di connections with other towns. The task is to
design the net of air connections among the towns in such a way that the
town Mi has exactly di connections with other towns.
We assume that connections are two-way and that each pair of towns has
at most one connection between them.
Task
Write a program that:
reads the number of towns n and the numbers
di from the text file LOT.IN,
designs the net of air connections in such a way that for every i, 1 <= i <= n,
the town Mi has exactly di connections with other towns,
writes the list of all connections to the file LOT.OUT.
We assume that for the given data a solution exists. If there exists more than
one solution the program should find only one.
Input
In the first line of the text file LOT.IN there is written one integer n,
3 <= n <= 500, which is the number of towns.
In the following n lines there are written positive integers
di (one integer in each line).
Output
Your program should write all the connections of the created net to the text file
LOT.OUT. The description of each connection consists of two positive integers separated
by a single space. These integers are the numbers of two connected towns. Each
description should be placed in a separate line. The numbers of towns in a line
can be written in an arbitrary order. Similarly, the order of connections is not
important.
Example
For the file:
6
2
3
2
4
1
2
an example of a correct solution is the file LOT.OUT