Hide

# Problem E

Early 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 |

CPU Time limit
4 seconds

Memory limit
1024 MB

Downloads

Author

Lewin Gan

Source
ICPC North America Regional Contests 2019-11-09