题目描述

设 $N$ 为一个正的偶数。

有一个排列 $p = (p_1, p_2, ..., p_N)$，其为 $1$ 到 $N$ 的一个排列。すぬけ君希望通过如下过程构造出一个 $1$ 到 $N$ 的排列 $q$：

首先，准备一个空序列 $q$。然后重复以下操作，直到 $p$ 变为空：

• 选择 $p$ 中相邻的两个元素，依次记为 $x$、$y$，将 $x$、$y$ 从 $p$ 中移除（此时 $p$ 长度减少 $2$），再将 $x$、$y$ 按顺序插入到 $q$ 的开头。

当 $p$ 为空时，$q$ 就是一个 $1$ 到 $N$ 的排列。

请你输出字典序最小的 $q$。

输入格式

输入从标准输入中以如下格式给出：

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

输出格式

请输出字典序最小的 $q$，各元素用空格分隔。

样例 1

输入

4
3 2 4 1

输出

3 1 2 4

样例 2

输入

2
1 2

输出

1 2

样例 3

输入

8
4 6 3 2 8 5 7 1

输出

3 1 2 7 4 6 8 5

说明/提示

限制条件

• $N$ 是偶数。
• $2 \leq N \leq 2 \times 10^5$
• $p$ 是 $1$ 到 $N$ 的一个排列。

样例说明 1

按照如下顺序操作即可：

$p\ \ \ \ \ q$

$(3, 2, 4, 1)\ \ \ \ ()$

$\downarrow\ \ \downarrow$

$(3, 1)\ \ \ (2, 4)$

$\downarrow\ \ \downarrow$

$()\ \ \ (3, 1, 2, 4)$

样例说明 3

可以按照如下操作完成：

$p\ \ \ \ \ q$

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

$\downarrow\ \ \downarrow$

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

$\downarrow\ \ \downarrow$

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

$\downarrow\ \ \downarrow$

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

$\downarrow\ \ \downarrow$

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

由 ChatGPT 5 翻译