2019 North Central NA Regional Contest

#### Start

2019-11-09 18:00 UTC

## 2019 North Central NA Regional Contest

#### End

2019-11-09 23:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -203 days 22:01:54

5:00:00

0:00:00

# Problem EEarly Orders

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