Early Orders

면접 대비

시간 제한4초메모리 제한1024 MB

요약

1부터 k까지의 모든 값이 적어도 한 번씩 등장하는 수열이 주어질 때, 각 값을 정확히 한 번씩 포함하는 부분 수열 가운데 사전순으로 가장 작은 것을 찾는다.

문제

정수 리스트 $x_1, x_2, \ldots, x_n$ 과 수 $k$ 가 주어진다. $1$ 부터 $k$ 까지의 각 정수 $i$ 는 리스트에 적어도 한 번 등장한다.

$x$ 의 부분 수열 중에서 $1$ 부터 $k$ 까지의 각 정수를 정확히 한 번씩 포함하는 것 가운데 사전순으로 가장 작은 것을 구하라.

첫째 줄에 두 정수 $n$ 과 $k$ 가 주어진다. $1 \le k \le n \le 200\,000$ 이다. 다음 $n$ 개의 줄에 각각 정수 $x_i$ 가 주어지며 $1 \le x_i \le k$ 이다.

$x$ 의 부분 수열 중에서 $1$ 부터 $k$ 까지의 각 정수를 정확히 한 번씩 포함하는 것 가운데 사전순으로 가장 작은 것을 공백으로 구분하여 한 줄에 출력한다.