Longest Increasing Subsequence K

Time limit0.25sMemory limit512 MB

Summary

Given a sequence of N integers and K, find the K-th longest increasing subsequence in lexicographic order of index sequences, or print -1 if fewer than K exist.

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

Problem

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

Two LISes $A_{i_1}, \ldots, A_{i_L}$ and $A_{j_1}, \ldots, A_{j_L}$ are different if there is at least one $k$ with $i_k \ne 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$

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 1 4 1 3 5
```
Expected output
```
1 3 5
```
Example 4
Input
```
6 2
2 1 4 1 3 5
```
Expected output
```
1 3 5
```
Example 5
Input
```
6 3
2 1 4 1 3 5
```
Expected output
```
1 4 5
```