C. Not-So-Long Increasing Subsequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$N, K$$$ be positive integers satisfying $$$K \leq N$$$. Busy Beaver has a permutation$$$^{\text{∗}}$$$ $$$a_1, \ldots, a_N$$$ of $$$1, \dots, N$$$. A length $$$K$$$ subsequence$$$^{\text{†}}$$$ of $$$a_1, \ldots, a_N$$$ given by $$$b_1, \ldots, b_K$$$ is interesting if the longest increasing$$$^{\text{‡}}$$$ subsequence of $$$b_1, \dots, b_K$$$ has length at most $$$\frac{K+1}{2}$$$.

Determine whether Busy Beaver's permutation has an interesting subsequence of length $$$K$$$, and if it exists, provide such an example of an interesting subsequence.

$$$^{\text{∗}}$$$A permutation of length $$$N$$$ is an array consisting of $$$N$$$ distinct integers from $$$1$$$ to $$$N$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$N=3$$$ but there is $$$4$$$ in the array).

$$$^{\text{†}}$$$A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements.

$$$^{\text{‡}}$$$A sequence $$$a_1, \dots, a_m$$$ is increasing if $$$a_1 \lt a_2 \lt \dots \lt a_{m-1} \lt a_m$$$. For instance, $$$[1, 2, 5]$$$ is increasing while $$$[2, 5, 1]$$$ is not.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, the number of test cases. The description of each test case follows.

The first line of each test case contains two space-separated integers $$$N, K$$$ ($$$1 \leq K \leq N \leq 2 \cdot 10^5$$$).

The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \leq a_i \leq N$$$, $$$a_i$$$ pairwise distinct) — Busy Beaver's permutation.

It is guaranteed that the sum of $$$N$$$ across all test cases is no more than $$$2 \cdot 10^5$$$.

Output

For each test case, output "YES" (without quotes) if there exists an interesting subsequence, and "NO" (without quotes) otherwise. You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Then, if you responded with "YES", print a second line consisting of $$$K$$$ space-separated integers $$$i_1, \dots, i_K$$$ ($$$1 \leq i_1 \lt \dots \lt i_K \leq n$$$), the indices of the permutation such that $$$a_{i_1}, \dots, a_{i_K}$$$ is an interesting subsequence. If there are multiple possible solutions, print any of them.

Scoring

You will receive $$$50\%$$$ of the points for each subtask if the YES/NO responses are correct, but the provided values of $$$i_1, \dots, i_K$$$ are not. For each test case, you must still output the indices $$$i_1 \lt \dots \lt i_K$$$ of a length-$$$K$$$ subsequence to receive partial credit for YES/NO responses. For instance, you could output $$$(i_1, \dots, i_K) = (1, \dots, K)$$$ but not $$$(i_1, \dots, i_K) = (1, \dots, 1)$$$.

There are three subtasks for this problem.

  • ($$$10$$$ points): $$$K \leq 4$$$.
  • ($$$20$$$ points): The permutation has at most one index $$$i$$$ ($$$1 \leq i \lt N$$$) such that $$$a_i \gt a_{i+1}$$$.
  • ($$$70$$$ points): No additional constraints.
Example
Input
10
4 2
4 2 1 3
7 3
3 1 4 5 7 2 6
8 8
4 5 6 7 8 1 2 3
6 4
5 2 4 3 1 6
9 8
1 3 2 4 6 5 7 9 8
9 7
1 3 2 4 6 5 7 9 8
9 5
1 6 8 9 2 5 3 4 7
3 2
3 2 1
3 2
1 2 3
1 1
1
Output
YES
2 3 
YES
5 6 7 
NO
YES
1 2 4 5 
NO
YES
2 3 5 6 7 8 9 
YES
3 4 6 7 8 
YES
2 3 
NO
YES
1
Note

In the first test case, the subsequence $$$[a_2, a_3] = [2, 1]$$$ has two longest increasing subsequences $$$[2]$$$ and $$$[1]$$$, each of which has length at most $$$\frac{2 + 1}{2} = \frac 32.$$$ It is therefore an interesting subsequence.

In the second test case, the subsequence $$$[a_5, a_6, a_7] = [7, 2, 6]$$$ has a unique longest increasing subsequence given by $$$[2, 6]$$$, which has length at most $$$\frac{3 + 1}{2} = 2.$$$ It is therefore an interesting subsequence.

In the third test case, the only subsequence of length $$$8$$$ is the entire sequence $$$[a_1, \dots, a_8] = [4, 5, 6, 7, 8, 1, 2, 3]$$$. The longest increasing subsequence of this sequence is $$$[4, 5, 6, 7, 8]$$$. As its length is greater than $$$\frac{8 + 1}{2} = \frac 92$$$, there is no interesting subsequence.