配点 : $800$ 点

問題文

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

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

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

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

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

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

制約

• $N$ は偶数である。
• $2 \leq N \leq 2 \times 10^5$
• $p$ は $(1, 2, ..., N)$ の順列である。

入力

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

$N$

$p_1$ $p_2$ $...$ $p_N$

出力

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

4
3 2 4 1

3 1 2 4

次の順に操作を行えばよいです。

2
1 2

1 2

8
4 6 3 2 8 5 7 1

3 1 2 7 4 6 8 5

次の順に操作を行えばよいです。