가장 긴 증가하는 부분 수열 k

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

요약

서로 다른 정수 N개가 주어질 때, 가장 긴 증가 부분 수열 중 사전순으로 K번째 수열을 구합니다. 그런 수열이 K개보다 적으면 -1을 출력합니다.

문제

N개의 정수로 이루어진 수열 $A_1, A_2, \ldots, A_N$ 에서, 가장 긴 증가하는 부분 수열(LIS)의 길이를 $L$ 이라고 하자. LIS는 하나 또는 그 이상 있을 수 있다. 모든 LIS를 사전 순으로 정렬했을 때, $K$ 번째 오는 수열을 구해보자.

두 LIS $A_{i_1}, A_{i_2}, \ldots, A_{i_L}$ 과 $A_{j_1}, A_{j_2}, \ldots, A_{j_L}$ 이 있을 때, $i_k \neq j_k$ 를 만족하는 $k$ 가 하나라도 존재하면 다른 LIS이다.

첫째 줄에 $N$ 과 $K$ 가 주어진다. 둘째 줄에 공백으로 구분된 $A_1, A_2, \ldots, A_N$ 이 주어진다.

$K$ 번째 LIS를 공백으로 구분해서 출력한다. $K$ 번째 LIS가 없을 때는 $-1$ 을 출력한다.