← 返回题目列表

AtCoder · arc165_f

F. 使相邻

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

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

  1. |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. 有一个整数 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