Leonhard Euler famously solved The Seven Bridges of Königsberg problem, leading to the establishment of graph theory. Overjoyed by the creation of a new branch of mathematics, Euler decided to pose himself a problem.

First, Euler gives himself ~N~ nodes and ~N-1~ edges to build a directed graph (a directed tree with all edges pointing away from root node), labelling each node from ~1~ to ~N~. The ~i^{th}~ node is assigned a value, ~V~, of ~\frac{1}{2^i}~. After doing so, he assigns a weight, ~W~, to each edge where ~W~ is equal to the sum of the values of all the nodes that would be disconnected if that edge were to be removed.

Ex: ~W=V_1+V_2+V_3~ if nodes ~1-3~ become disconnected.

Note that in the above sample ~V_1 = \frac{1}{2}~, ~V_2=\frac{1}{4}~ and so on.

He decides to order these edges by weight from greatest to least (decreasing order) and writes down which node the edges come from (if ~1~ goes to ~2~, Euler would write down ~1~). Unfortunately, Euler was distracted by a different mathematical problem and came back to find his graph missing. However, he still has his written notes! Can you help Euler reconstruct his original graph?

Input Specifications

The first line of input contains ~N(2\le N \le 10^3)~ representing the number of nodes.

The second line of input contains ~N-1~ integers, ~a_1,a_2,...,a_{n-1} (1 \le a \le N)~ where ~a~ is the node from which the ~i^{th}~ edge came from. Edges are given in decreasing order of weight.

Output Specifications

In decreasing order of weight, output ~N-1~ lines each representing an edge in the form a b where ~a~ and ~b~ are two valid nodes and a<b.

Sample Input

6
6 3 6 2 3

Sample Output

3 6
1 3
2 6
2 4
3 5

Explanation