P9928 [NFLSPC #6] A Less “Unhinged” Statement

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$.

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.

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$).

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