/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 以上 M 以下の整数からなる長さ N の数列 A があります。ここで、1 以上 M 以下のどの整数も A に 1 回以上登場します。
A の長さ M の（連続とは限らない）部分列であって 1, \ldots, M が 1 回ずつ登場するもののうち、辞書順最小のものを答えてください。
制約
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq M
- 1 以上 M 以下のどの整数も A に 1 回以上登場する。
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
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 が 1 回ずつ登場するものは (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
Score : 600 points
Problem Statement
We have a sequence A of length N consisting of integers between 1 and M. Here, every integer from 1 to M 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