← 返回题目列表

AtCoder · abc299_g

G. 最小排列

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

分数: 600 点

问题陈述

我们有一个序列 A 长度 N 由之间的整数组成 1 和 M。这里,每个整数 1 to M 至少出现一次 A.

其中长度-M 的子序列 A 其中每个 1, \ldots, M 出现一次,找到字典顺序最小的一个。

约束

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq M
  • 之间的每个整数 1 和 M,包含在内,至少出现一次 A.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \ldots A_N

输出

让 B_1, \ldots, B_M 为查找的子序列,并按以下格式打印:

B_1 B_2 \ldots B_M

示例输入 1

4 3
2 3 1 3

示例输出 1

2 1 3

长度-3 的子序列 A 其中每个 1, 2, 3 出现一次是 (2, 3, 1) 和 (2, 1, 3)。其中按字典顺序排列较小的是 最多 (2, 1, 3).


示例输入 2

4 4
2 3 1 4

示例输出 2

2 3 1 4

示例输入 3

20 10
6 3 8 5 8 10 9 3 6 1 8 3 3 7 4 7 2 7 8 5

示例输出 3

3 5 8 10 9 6 1 4 2 7