Early Orders

Interview

Time limit4sMemory limit1024 MB

Summary

Given a sequence where every value from 1 to k appears at least once, find the lexicographically smallest subsequence that contains each of those k values exactly once.

Level: Medium6 of 10
Topics: Stack, Greedy, Array, Hash map
Solved: No attempts yet

Problem

You are given a list of integers $x_1, x_2, \ldots, x_n$ and a number $k$ . Every integer $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

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

Examples2

Example 1
Input
```
6 3
3
2
1
3
1
3
```
Expected output
```
2 1 3
```
Example 2
Input
```
10 5
5
4
3
2
1
4
1
1
5
5
```
Expected output
```
3 2 1 4 5
```