给定正偶数 $N$。

给定 $N$ 元排列 $p = (p_1, p_2, ..., p_N)$. Snuke 打算根据下述步骤构造一个 $N$ 元排列 $q$。

首先，令 $q$ 为空。接下来，执行下述操作直到 $p$ 为空。

• 选择 $p$ 中两个相邻元素 ,按原顺序设它们是 $x$ 和 $y$. 从 $p$ 中移除 $x$ 和 $y$，将它们按顺序接在 $q$ 的前面。

试求可能的形成的 $q$ 中，字典序最小的排列。