Problem Statement

You are given a permutation $(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$. Place $N$ points $(i,P_i)$ on the coordinate plane.

When $2$ points $A=(a_1,a_2),B=(b_1,b_2)$ satisfy $a_1\lt b_1$ and $a_2\lt b_2$, we say that $B$ is in the shadow of $A$.

Perform the following operation.

1. Among the points currently on the plane, let $S$ be the set of points that are not in the shadow of any point.
2. Output the minimum $x$-coordinate and the minimum $y$-coordinate of the points in $S$.
3. Remove the points in $S$ from the plane.
4. If there are no points on the plane, terminate; otherwise, return to 1.

Constraints

• $1\le N\le 2\times 10^5$
• $(P_1,P_2,\ldots,P_N)$ is a permutation of $(1,2,\ldots,N)$
• All inputs are integers

Input

$N$
$P_1$ $P_2$ $\cdots$ $P_N$

Output

Let $M$ be the number of outputs, and let $x_i, y_i$ be the minimum $x$-coordinate and the minimum $y$-coordinate, respectively, in the $i$-th output. Print in the following format.

$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_M$ $y_M$

Sample

5
2 4 3 1 5

1 1
2 3
5 5

4
4 3 2 1

1 1

9
9 6 4 2 8 5 3 1 7

1 1
5 3
9 7