分数: 600 点
问题陈述
给定的是一个整数序列 a 长度 2N.
Snuke 将使用 非空 (不一定连续)子序列 x=(x_1,x_2,\ldots,x_k) of (1,2, \ldots, N)。 该序列将通过提取并连接 x_1-th, x_2-th, \ldots, x_k-th, (x_{1}+N)-th, \ldots, (x_{k}+N)第一个元素 a 按此顺序。
找到 Snuke 可以生成的字典顺序最小的序列。
序列的词典顺序
这是确定不同序列之间的字典顺序的算法 S 和 T.
下面,让 S_i 表示 i- 第一个元素 S。另外,如果 S 按字典顺序小于 T,我们将该事实表示为 S \lt T;如果 S 按字典顺序大于 T,我们将该事实表示为 S \gt T.
- 让 L 是以下长度中较小的一个 S 和 T。对于每个 i=1,2,\dots,L,我们检查是否 S_i 和 T_i 是相同的。
- 如果有 i 这样 S_i \neq T_i,让 j 是最小的这样 i。然后,我们比较 S_j 和 T_j。如果 S_j 小于 T_j 按数字顺序,我们确定 S \lt T 然后退出;如果 S_j 大于 T_j,我们确定 S \gt T 然后退出。
- 如果没有 i 这样 S_i \neq T_i,我们比较长度 S 和 T。如果 S 短于 T,我们确定 S \lt T 然后退出;如果 S 长于 T,我们确定 S \gt T 然后退出。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 1 \leq a_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N
a_{1} \cdots a_{2N}
输出
打印 Snuke 可以生成的字典顺序最小的序列。
示例输入 1
3 2 1 3 1 2 2
示例输出 1
1 2
- 我们选择 x = (2).
- 然后,结果序列将是 (1,2),字典顺序上最小的可能结果。
示例输入 2
10 38 38 80 62 62 67 38 78 74 52 53 77 59 83 74 63 80 61 68 55
示例输出 2
38 38 38 52 53 77 80 55
示例输入 3
12 52 73 49 63 55 74 35 68 22 22 74 50 71 60 52 62 65 54 70 59 65 54 60 52
示例输出 3
22 22 50 65 54 52