AT_arc080_c [ARC080E] Young Maids

设 $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$，各元素用空格分隔。

## 限制条件 - $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 翻译