Sample Input

6
6 3 6 2 3

Sample Output

3 6
1 3
2 6
2 4
3 5

Explanation

Consider the input number by number.

6: This tells us the root node. It also tells us the edge of the greatest weight comes from 6.

6 3: This tells us that the edge of second greatest weight comes from 3. It also tells us the edge of the greatest weight goes from 6 to 3. Why? 6 as a node, is never calculated in the weight of any edge. For any edge, the only node not considered is the one it comes from. This implies that if the edge of second greatest weight comes from 3, the edge of greatest weight must contain 3 (as it is the only node possible).

6 3 6: If we attempt to apply the idea above, we run into an issue. An edge from 6 is the third greatest weight. 3 can obviously not lead to 6 so this raises two questions:

1. What number does 3 lead to?
2. What number does this new edge from 6 lead to?

We should notice that we have now reached the end of a branch. The edge from 3 must lead to a leaf node. There is only one way to guarantee that the edge from 3 will be of third greatest weight. That is to choose the smallest number not currently in use as the node. The reasoning for this is can be seen in the below infinite series:

~\frac12+\frac14+\frac18+\frac{1}{16}+\cdots = \sum_{n=1}^\infty \left({\frac 12}\right)^n = \frac {\frac12}{1-\frac 12} = 1.~

In this question, the smallest fraction is ~\frac{1}{2^{1000}}~, meaning if we take the above series and change it slightly:

~\frac12+\frac14+\frac18+\frac{1}{16}+\cdots+\frac{1}{2^{1000}} < 1.~

We can use this to prove that

~\frac14+\frac18+\frac{1}{16}+\cdots+\frac{1}{2^{1000}} < 1/2~ and ~\frac18+\frac{1}{16}+\cdots+\frac{1}{2^{1000}} < 1/4~ and so on.

meaning that for every edge of weight ~\frac{1}{2^n}~, there will never be any branches made up of nodes ~>n~ which will have a greater weight.

Final solution (greedy).

Reading in the input, the ending point for each node is the next node unless the next node is already a part of the tree. If the next node is on the tree already, the ending point is the smallest number not yet assigned.