問題文

$N$ を正の偶数とします。

$(1, 2, \dots N)$ の順列 $p=(p_1, p_2, \dots, p_N)$ があります。とらお君は、次の手続きによって $(1, 2, \dots, N)$ の順列 $q$ を作ろうとしています。

まず、空の数列 $q$ を用意します。 $p$ が空になるまで、次の操作を繰り返します。

• $p$ の隣り合う $2$ つの要素を選び、 $x, y$ とする。 $x, y$ を $p$ から取り除き (このとき、$p$ は $2$ だけ短くなる)、$x, y$ をこの順のまま $q$ の末尾へ追加する。

$p$ が空になったとき、$q$ は $(1,2,...,N)$ の順列になっています。

辞書順で最小の $q$ を求めてください。

制約

• $N$ は偶数である。
• $2 \le N \le 2\times 10^5$
• $(p_1, p_2, \dots, p_N)$ は $(1, 2, \dots, N)$ の順列である。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$p_1$ $p_2$ $\dots$ $p_N$

出力

辞書順で最小の $q$ を空白区切りで出力せよ。

サンプル

4
3 2 4 1

2 4 3 1

$p$                  $q$
$(3, 2, 4, 1)$          $()$
$(3, 1)$              $(2, 4)$ 
$()$                 $(2, 4, 3, 1)$ 

2
1 2

1 2

8
4 6 3 2 8 5 7 1

2 8 3 5 4 6 7 1