CF1283F.DIY Garland

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?

波利卡普决定装饰自己的房间，因为新年即将到来。他将安装的主要装饰品之一，就是他自己焊接的彩灯串。

对于波利卡普而言，仅由若干灯泡通过一根导线连接而成的简单彩灯串太过乏味。他计划焊接一个由 $n$ 个灯泡和 $n - 1$ 根导线组成的彩灯串。其中恰好有一个灯泡直接接入电网，其余灯泡则通过导线从该灯泡获取电力。每根导线恰好连接两个灯泡；其中一个灯泡称为该导线的主灯（即从其他导线获取电力，并将电力传输给本导线），另一个称为辅灯（即从本导线获取电力）。显然，每个灯泡至多只有一根导线向其供电（该灯泡即为该导线的辅灯，而对所有其他直接与其相连的导线而言，它均为主灯）。

每个灯泡具有一个亮度值：第 $i$ 个灯泡的亮度为 $2^i$。我们定义某根导线的重要性为：若切断该导线（其余导线均正常工作），则所有与电网断开连接的灯泡的亮度值之和。

波利卡普已画出了他想要制作的彩灯串的设计图（图中包含全部 $n$ 个灯泡与 $n - 1$ 根导线，并标出了将直接接入电网的灯泡；导线的布置方式保证了电力可传输至每个灯泡）。随后，波利卡普计算了每根导线的重要性，将这些导线按重要性降序排列并编号为 $1$ 至 $n - 1$，最后按此顺序（即从第 $1$ 根导线到第 $n-1$ 根导线）写下每根导线的主灯编号。

次日，波利卡普购买了彩灯串所需的所有元件，准备开始焊接——但他却找不到原先的设计图。幸运的是，波利卡普找到了记录所有导线主灯编号的列表。你能帮他恢复原始的设计图吗？

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).

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 灯的数量。

第二行包含 $n - 1$ 个整数 $a_1$, $a_2$, ..., $a_{n - 1}$（$1 \le a_i \le n$），其中 $a_i$ 表示第 $i$ 根导线的主灯编号（导线按重要性降序编号）。

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.

如果无法还原原始方案，则输出一个整数 $-1$。

否则，按如下方式输出该方案：第一行输出一个整数 $k$（$1 \le k \le n$），表示连接至电网的灯的编号；随后输出 $n - 1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，且 $x_i \ne y_i$），表示由某根导线连接的两盏灯的编号。导线（以及由导线连接的灯）的描述顺序可以任意。所输出的描述必须对应一个花环方案，使得 Polycarp 能够从中写出列表 $a_1$, $a_2$, ..., $a_{n - 1}$。若存在多个满足条件的方案，输出其中任意一个即可。

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

第一个示例的电路图（R 表示连接到电网的灯泡，导线上的数字表示其重要性值）：