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

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

요약

정수 수열과 K가 주어졌을 때, 인덱스 순서의 사전순으로 K번째 최장 증가 부분수열을 구하는 문제입니다. 그런 수열이 K개보다 적으면 -1을 출력합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 이분 탐색, 조합론
정답자: 아직 제출이 없습니다

문제

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

두 LIS $A_{i_1}, \ldots, A_{i_L}$ 와 $A_{j_1}, \ldots, A_{j_L}$ 은 $i_k \ne j_k$ 를 만족하는 $k$ 가 하나라도 있으면 서로 다른 LIS이다.

입력

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

출력

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

제한

$1 \le N \le 10^5$
$1 \le K \le 10^{18}$
$1 \le A_i \le N$

예제5

예제 1
입력
```
5 1
1 4 2 3 5
```
예상 출력
```
1 2 3 5
```
예제 2
입력
```
5 2
1 4 2 3 5
```
예상 출력
```
-1
```
예제 3
입력
```
6 1
2 1 4 1 3 5
```
예상 출력
```
1 3 5
```
예제 4
입력
```
6 2
2 1 4 1 3 5
```
예상 출력
```
1 3 5
```
예제 5
입력
```
6 3
2 1 4 1 3 5
```
예상 출력
```
1 4 5
```