← 返回题目列表

AtCoder · arc134_d

D. 连接子序列

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

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

  1. 让 L 是以下长度中较小的一个 S 和 T。对于每个 i=1,2,\dots,L,我们检查是否 S_i 和 T_i 是相同的。
  2. 如果有 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 然后退出。
  3. 如果没有 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