← 返回题目列表

AtCoder · arc080_c

E. 年轻女仆

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

让 N 是正偶数。

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

首先,让 q 是一个空序列。 然后,执行以下操作,直到 p 变为空:

  • 选择两个相邻元素 p,并打电话给他们 x 和 y 按顺序。删除 x 和 y 来自 p (减少长度 p by 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)