問題文

$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 ≤ N ≤ 2 × 10^5$
• $p$ は $(1, 2, ..., N)$ の順列である。

---

入力

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

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

出力

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

---

入力例 1

4
3 2 4 1

出力例 1

3 1 2 4

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

$p$

$q$

$(3, 2, 4, 1)$

$()$

↓

↓

$(3, 1)$

$(2, 4)$

↓

↓

$()$

$(3, 1, 2, 4)$

---

入力例 2

2
1 2

出力例 2

1 2

---

入力例 3

8
4 6 3 2 8 5 7 1

出力例 3

3 1 2 7 4 6 8 5

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

$p$

$q$

$(4, 6, 3, 2, 8, 5, 7, 1)$

$()$

↓

↓

$(4, 6, 3, 2, 7, 1)$

$(8, 5)$

↓

↓

$(3, 2, 7, 1)$

$(4, 6, 8, 5)$

↓

↓

$(3, 1)$

$(2, 7, 4, 6, 8, 5)$

↓

↓

$()$

$(3, 1, 2, 7, 4, 6, 8, 5)$