Hide

Problem E
Early Orders

/problems/earlyorders/file/statement/en/img-0001.png

You are given a list of integers $x_1, x_2, \ldots , x_ n$ and a number $k$. It is guaranteed that each $i$ from $1$ to $k$ appears in the list at least once.

Find the lexicographically smallest subsequence of $x$ that contains each integer from $1$ to $k$ exactly once.

Input

The first line contains two integers $n$ and $k$, with $1\le k\le n\le 200\, 000$. The following $n$ lines each contain an integer $x_ i$ with $1\le x_ i\le k$.

Output

Write out on one line, separated by spaces, the lexicographically smallest subsequence of $x$ that has each integer from $1$ to $k$ exactly once.

Sample Input 1 Sample Output 1
6 3
3
2
1
3
1
3
2 1 3
Sample Input 2 Sample Output 2
10 5
5
4
3
2
1
4
1
1
5
5
3 2 1 4 5

Please log in to submit a solution to this problem

Log in