One of Each

면접 대비

시간 제한2초메모리 제한512 MB

요약

1부터 k까지의 값이 모두 한 번 이상 나타나는 수열에서 각 값을 정확히 한 번씩 포함하는 사전순으로 가장 작은 부분수열을 찾는다.

문제

n개의 정수로 이루어진 수열 X = [x1, x2, ..., xn]와 정수 k가 주어진다. 1 ≤ xi ≤ k이며, 1부터 k까지의 모든 정수가 X에 적어도 한 번씩 나타난다.

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

첫째 줄에 두 정수 n과 k가 주어진다 (1 ≤ k ≤ n ≤ 2 ∙ 105). n은 수열의 길이이며, 수열은 1부터 k까지의 정수로만 이루어진다.

다음 n개의 줄에 각각 하나의 정수 xi가 주어진다 (1 ≤ xi ≤ k). 이들이 수열 X의 값들이다. 1부터 k까지의 모든 값이 X에 적어도 한 번씩 나타난다.

1부터 k까지의 모든 값을 포함하는 X의 부분수열 중 사전순으로 가장 작은 것을 공백으로 구분하여 한 줄에 출력한다.