AT_abc299_g [ABC299G] Minimum Permutation

题目描述

有一个长度为 $N$ 的数列 $A$，其中每个元素都是 $1$ 到 $M$ 之间的整数。并且，$1$ 到 $M$ 之间的每个整数在 $A$ 中至少出现一次。

请你在 $A$ 的所有长度为 $M$ 的（不一定连续的）子序列中，找出恰好包含 $1,\ 2,\ \ldots,\ M$ 各出现一次的子序列，并输出其中字典序最小的一个。

输入格式

输入以以下格式从标准输入读入。

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

输出格式

请将所求的子序列记为 $B_1,\ B_2,\ \ldots,\ B_M$，按以下格式输出。

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

输入输出样例 #1

输入 #1

4 3
2 3 1 3

输出 #1

2 1 3

输入输出样例 #2

输入 #2

4 4
2 3 1 4

输出 #2

2 3 1 4

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $1 \leq M \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq M$
• $1$ 到 $M$ 之间的每个整数在 $A$ 中至少出现一次。
• 输入中的所有数值均为整数。

样例解释 1

$A$ 的所有长度为 $3$ 的子序列中，恰好包含 $1,\ 2,\ 3$ 各出现一次的有 $(2,\ 3,\ 1)$ 和 $(2,\ 1,\ 3)$，其中字典序最小的是 $(2,\ 1,\ 3)$。

由 ChatGPT 4.1 翻译