Longest Increasing Subsequence K

Time limit0.25sMemory limit512 MB

Summary

Given N distinct integers, print the K-th lexicographically smallest longest increasing subsequence, or -1 if there are fewer than K of them.

Level: Medium7 of 10
Topics: Dynamic programming, Binary search, Sorting
Solved: No attempts yet

Problem

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

Two LIS $A_{i_1}, A_{i_2}, \ldots, A_{i_L}$ and $A_{j_1}, A_{j_2}, \ldots, A_{j_L}$ are different if there is at least one $k$ with $i_k \neq j_k$ .

Input

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

Output

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

Constraints

$1 \le N \le 10^5$
$1 \le K \le 10^{18}$
$1 \le A_i \le N$
No two elements of the sequence $A$ are equal.

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
```