DIY Garland
Contest: Codeforces Round 611 (Div. 3)
Difficulty rating: 2200
Tags: constructive algorithms, greedy, trees

Polycarp has decided to decorate his room because the New Year is soon. One of the main decorations that Polycarp will install is the garland he is going to solder himself.

Simple garlands consisting of several lamps connected by one wire are too boring for Polycarp. He is going to solder a garland consisting of $$$n$$$ lamps and $$$n - 1$$$ wires. Exactly one lamp will be connected to power grid, and power will be transmitted from it to other lamps by the wires. Each wire connectes exactly two lamps; one lamp is called the main lamp for this wire (the one that gets power from some other wire and transmits it to this wire), the other one is called the auxiliary lamp (the one that gets power from this wire). Obviously, each lamp has at most one wire that brings power to it (and this lamp is the auxiliary lamp for this wire, and the main lamp for all other wires connected directly to it).

Each lamp has a brightness value associated with it, the $$$i$$$-th lamp has brightness $$$2^i$$$. We define the importance of the wire as the sum of brightness values over all lamps that become disconnected from the grid if the wire is cut (and all other wires are still working).

Polycarp has drawn the scheme of the garland he wants to make (the scheme depicts all $$$n$$$ lamp and $$$n - 1$$$ wires, and the lamp that will be connected directly to the grid is marked; the wires are placed in such a way that the power can be transmitted to each lamp). After that, Polycarp calculated the importance of each wire, enumerated them from $$$1$$$ to $$$n - 1$$$ in descending order of their importance, and then wrote the index of the main lamp for each wire (in the order from the first wire to the last one).

The following day Polycarp bought all required components of the garland and decided to solder it — but he could not find the scheme. Fortunately, Polycarp found the list of indices of main lamps for all wires. Can you help him restore the original scheme?

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of lamps.

The second line contains $$$n - 1$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n - 1}$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the index of the main lamp for the $$$i$$$-th wire (wires are numbered in descending order of importance).

Output format:
If it is impossible to restore the original scheme, print one integer $$$-1$$$.

Otherwise print the scheme as follows. In the first line, print one integer $$$k$$$ ($$$1 \le k \le n$$$) — the index of the lamp that is connected to the power grid. Then print $$$n - 1$$$ lines, each containing two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — the indices of the lamps connected by some wire. The descriptions of the wires (and the lamps connected by a wire) can be printed in any order. The printed description must correspond to a scheme of a garland such that Polycarp could have written the list $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n - 1}$$$ from it. If there are multiple such schemes, output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The scheme for the first example (R denotes the lamp connected to the grid, the numbers on wires are their importance values):

Example input:
6
3 6 3 1 5

Example output:
3
6 3
6 5
1 3
1 4
5 2

Editorial:
First of all, we don't like the fact that importance values can be integers up to $$$2^n$$$ (it is kinda hard to work with them). Let's rephrase the problem.
The highest bit set to $$$1$$$ in the importance value denotes the maximum in the subtree rooted at the auxiliary lamp for the wire. So, we sort the wires according to the maximums in their subtrees. To break ties, we could consider the second maximum, then the third maximum — but that's not convenient. We can use something much easier: suppose there are two vertices with the same maximum in their subtrees; these vertices belong to the path from the root to the maximum in their subtrees, and the one which is closer to the root has the greater importance value. So, to get the order described in the problem statement, we could sort the vertices according to the maximum in their subtrees, and use depth as the tie-breaker.
What does this imply? All vertices of some prefix are ancestors of vertex $$$n$$$, so some prefix denotes the path from the root to $$$n$$$ (excluding $$$n$$$ itself). Then there are some values describing the path from some already visited vertex to $$$n - 1$$$ (if $$$n - 1$$$ was not met before), then to $$$n - 2$$$, and so on.
How can we use this information to restore the original tree? $$$a_1$$$ is the root, obviously. Then the sequence can be separated into several subsegments, each representing a vertical path in the tree (and each vertex is the parent of the next vertex in the sequence, if they belong to the same subsegment). How can we separate these vertices into subsegments, and how to find the parents for vertices which did not appear in the sequence at all? Suppose some vertex appears several times in our sequence. The first time it appeared in the sequence, it was in the middle of some vertical path, so the previous vertex is its parent; and every time this vertex appears again, it means that we start a new path — and that's how decomposition into paths is done.
Determining the parents of vertices that did not appear in the sequence is a bit harder, but can also be done. Let's recall that our sequence is decomposed into paths from root to $$$n$$$, from some visited vertex to $$$n - 1$$$, from some visited vertex to $$$n - 2$$$, and so on; so, each time the path changes, it means that we have found the maximum vertex (among unvisited ones). So we should keep track of the maximum vertex that was not introduced in the sequence while we split it into paths, and each time a path breaks, it means that we found the vertex we were keeping track of.
Overall, this solution can be implemented in $$$O(n)$$$.