Problem Description

Given a permutation $p$ of $1\sim n$ and an integer $k$, you need to find a subsequence $\{p_{i_1}, p_{i_2}, \cdots, p_{i_m}\}$ of $p$ ($1\le i_1 < i_2 < \cdots < i_m\le n$) such that:

• There are exactly $k$ integers $j$ satisfying $1\le j\le m$ and $p_{i_j}$ is the $j$-th smallest among $p_{i_1}, p_{i_2}, \cdots, p_{i_m}$.

If there are multiple solutions, output any one of them. If there is no valid subsequence, output $-1$.

Input Format

The first line contains two integers $n, k$.

The next line contains $n$ integers $p_1, p_2, \cdots, p_n$, representing the given permutation.

Output Format

If there is no solution, output one line with the integer $-1$.

Otherwise, output an integer $m$ in the first line, the length of the subsequence. You must ensure $1\le m\le n$.

In the next line, output $m$ integers $i_1, i_2, \cdots, i_m$, the indices of the subsequence. You must ensure $1\le i_j\le n$ and $i_j < i_{j+1}$ ($1\le j < m$).

4 1
4 2 1 3

3
2 3 4

Hint

For all testdata, $1\le n\le 10 ^ 5$, $1\le k\le n$, and $p_1, p_2, \cdots, p_n$ is a permutation of $1\sim n$.

• Subtask 1 ($10$ points): $n\leq 20$.
• Subtask 2 ($10$ points): $k = 2$.
• Subtask 3 ($30$ points): $k = 3$.
• Subtask 4 ($30$ points): $n\leq 10 ^ 3$.
• Subtask 5 ($20$ points): no special constraints.

Source: NFLSPC #6 D by tzc_wk

Translated by ChatGPT 5