分数: 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) |