102996: [Atcoder]ABC299 G - Minimum Permutation

Problem Statement

We have a sequence $A$ of length $N$ consisting of integers between $1$ and $M$. Here, every integer from $1$ to $N$ appears at least once in $A$.

Among the length-$M$ subsequences of $A$ where each of $1, \ldots, M$ appears once, find the lexicographically smallest one.

Constraints

• $1 \leq M \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq M$
• Every integer between $1$ and $M$, inclusive, appears at least once in $A$.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Let $B_1, \ldots, B_M$ be the sought subsequence, and print it in the following format:

$B_1$ $B_2$ $\ldots$ $B_M$

Sample Input 1

4 3
2 3 1 3

Sample Output 1

2 1 3

The length-$3$ subsequences of $A$ where each of $1, 2, 3$ appears once are $(2, 3, 1)$ and $(2, 1, 3)$. The lexicographically smaller among them is $(2, 1, 3)$.

Sample Input 2

4 4
2 3 1 4

Sample Output 2

2 3 1 4

Sample Input 3

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

Sample Output 3

3 5 8 10 9 6 1 4 2 7

问题描述

我们有一个长度为$N$的序列$A$，其中包含$1$到$M$之间的整数。在这里，$1$到$M$中的每个整数在$A$中至少出现一次。

在$A$的长度为$M$的子序列中，每个数字$1, \ldots, M$出现一次，找到字典序最小的一个。

限制条件

• $1 \leq M \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq M$
• 每个在$1$到$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

$A$的长度为$3$的子序列，其中每个数字$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