問題文

$(1,2,\ldots,N)$ の順列 $(P_1,P_2,\ldots,P_N)$ が与えられます。座標平面上に $N$ 個の点 $(i,P_i)$ を配置します。

$2$ 点 $A=(a_1,a_2),B=(b_1,b_2)$ が $a_1\lt b_1$ かつ $a_2\lt b_2$ をみたすとき、$B$ は $A$ の影にあるといいます。

次の操作を行ってください。

1. 現在平面上にある点について、どの点の影にもないような点の集合を $S$ とする。
2. $S$ の点の $x$ 座標の最小値と $y$ 座標の最小値を出力する。
3. 平面上から $S$ の点を削除する。
4. 平面上に点がなければ終了し、そうでなければ 1. に戻る。

制約

• $1\le N\le 2\times 10^5$
• $(P_1,P_2,\ldots,P_N)$ は $(1,2,\ldots,N)$ の順列
• 入力はすべて整数

入力

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

出力

出力回数を $M$、$i$ 回目の出力における $x$ 座標の最小値と $y$ 座標の最小値をそれぞれ $x_i, y_i$ とするとき、以下の形式で出力してください。

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

サンプル

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