시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.25 초 512 MB 77 7 6 17.647%

문제

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

두 LIS Ai1, Ai2, ..., AiL와 Aj1, Aj2, ..., AjL이 있을 때, ik ≠ jk를 만족하는 k가 하나라도 존재하면 다른 LIS이다.

입력

첫째 줄에 N과 K가 주어진다. 둘째 줄에 공백으로 구분된 A1, A2, ..., AN이 주어진다. 

출력

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

제한

  • 1 ≤ N ≤ 105
  • 1 ≤ K ≤ 1018
  • 1 ≤ Ai ≤ N

예제 입력 1

5 1
1 4 2 3 5

예제 출력 1

1 2 3 5

예제 입력 2

5 2
1 4 2 3 5

예제 출력 2

-1

예제 입력 3

6 1
2 1 4 1 3 5

예제 출력 3

1 3 5

예제 입력 4

6 2
2 1 4 1 3 5

예제 출력 4

1 3 5

예제 입력 5

6 3
2 1 4 1 3 5

예제 출력 5

1 4 5

예제 입력 6

6 4
2 1 4 1 3 5

예제 출력 6

2 3 5

예제 입력 7

6 5
2 1 4 1 3 5

예제 출력 7

2 4 5

예제 입력 8

6 6
2 1 4 1 3 5

예제 출력 8

-1

출처