Longest Increasing Subsequence ks

Time limit0.25sMemory limit512 MB

Summary

Given a permutation-like sequence, find the K-th longest increasing subsequence when all LISs are sorted lexicographically by index, or -1 if fewer than K exist.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Combinatorics, Binary search
Solved: No attempts yet

Problem

For a sequence of $N$ integers $A_1, A_2, \dots, A_N$ , let $L$ be the length of the longest increasing subsequence (LIS). There may be one or more LISs. Sort all LISs in lexicographic order and find the K-th one.

Given two LISs $A_{i_1}, A_{i_2}, \dots, A_{i_L}$ and $A_{j_1}, A_{j_2}, \dots, A_{j_L}$ , they are different LISs if there is at least one $k$ with $i_k \ne j_k$ .

Input

The first line gives N and K. The second line gives $A_1, A_2, \dots, A_N$ separated by spaces.

Output

Print the K-th LIS separated by spaces. If the K-th LIS does not exist, print -1.

Constraints

$1 \le N \le 500$
$1 \le K \le 10^9$
$1 \le A_i \le N$
The sequence A has no duplicate numbers.

Examples5

Example 1
Input
```
5 1
1 4 2 3 5
```
Expected output
```
1 2 3 5
```
Example 2
Input
```
5 2
1 4 2 3 5
```
Expected output
```
-1
```
Example 3
Input
```
6 1
2 6 4 1 3 5
```
Expected output
```
1 3 5
```
Example 4
Input
```
6 2
2 6 4 1 3 5
```
Expected output
```
2 3 5
```
Example 5
Input
```
6 3
2 6 4 1 3 5
```
Expected output
```
2 4 5
```