分数: 800 点
问题陈述
长度的整数序列 2n, X=(X_1,X_2,\dots,X_{2n}),这样 X_{2i-1}=X_{2i} 对于每个 i=1,2,\dots,n 被称为 好的序列.
存在一个长度为整数的序列 2N, A=(A_1,A_2,\dots,A_{2N}),其中包含每个整数 i=1,2,\dots,N 正好两次。
我们想要 A a 好的序列 通过执行交换两个相邻项的值零次或多次的操作。
让 K 是我们必须执行操作才能完成的最小操作数 A a 好的序列。找到字典顺序最小的 好的序列 可以通过执行操作获得 K 次 A.
序列的字典顺序是什么?
一个序列 当满足以下条件时, S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比 T = (T_1,T_2,\ldots,T_{|T|}) 当下面的 1. 或 2. 成立时。 在这里, |S| 和 |T| 表示的长度 S 和 T。
- |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- 有一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 满足以下两个条件:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i 小于 T_i (作为数字)。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- A 包含每个整数 i=1,2,\dots,N 正好两次。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \dots A_{2N}
输出
打印字典顺序最小的 好的序列 可以通过执行操作获得 K 次 A,之间有空格。
示例输入 1
3 3 2 1 2 3 1
示例输出 1
2 2 3 3 1 1
例如,我们可以执行四次操作,如下所示 (3,2,1,2,3,1) \rightarrow (3,2,1,3,2,1) \rightarrow (3,2,3,1,2,1) \rightarrow (3,3,2,1,2,1) \rightarrow (3,3,2,2,1,1) 使 A a 好的序列。该数字是所需的最小值。通过四个操作,我们还可以得到 A=(2,2,3,3,1,1),答案是 (2,2,3,3,1,1).
示例输入 2
3 1 1 2 2 3 3
示例输出 2
1 1 2 2 3 3
示例输入 3
15 15 12 11 10 5 11 13 2 6 14 3 6 5 14 10 15 1 2 13 9 7 4 9 1 3 8 12 4 8 7
示例输出 3
11 11 5 5 6 6 10 10 14 14 15 15 2 2 12 12 13 13 1 1 3 3 9 9 4 4 7 7 8 8