题目描述

设 $N$ 是一个正偶数。

我们有一个序列 $(1, 2, ..., N)$ 的排列，记为 $p = (p_1, p_2, ..., p_N)$。Snuke 正在按照以下步骤构造另一个序列 $(1, 2, ..., N)$ 的排列 $q$。

首先，令 $q$ 为空序列。然后，执行以下操作，直到 $p$ 变为空序列：

• 在 $p$ 中选择两个相邻的元素，并按顺序称之为 $x$ 和 $y$。从 $p$ 中删除 $x$ 和 $y$（将 $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$

输出格式

以空格为分隔打印字典序最小的排列。

---

示例输入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)$