Fixed Points
Contest: Codeforces Round 734 (Div. 3)
Difficulty rating: 2000
Tags: binary search, brute force, dp

Consider a sequence of integers $$$a_1, a_2, \ldots, a_n$$$. In one move, you can select any element of the sequence and delete it. After an element is deleted, all elements to the right are shifted to the left by $$$1$$$ position, so there are no empty spaces in the sequence. So after you make a move, the sequence's length decreases by $$$1$$$. The indices of the elements after the move are recalculated.

E. g. let the sequence be $$$a=[3, 2, 2, 1, 5]$$$. Let's select the element $$$a_3=2$$$ in a move. Then after the move the sequence will be equal to $$$a=[3, 2, 1, 5]$$$, so the $$$3$$$-rd element of the new sequence will be $$$a_3=1$$$ and the $$$4$$$-th element will be $$$a_4=5$$$.

You are given a sequence $$$a_1, a_2, \ldots, a_n$$$ and a number $$$k$$$. You need to find the minimum number of moves you have to make so that in the resulting sequence there will be at least $$$k$$$ elements that are equal to their indices, i. e. the resulting sequence $$$b_1, b_2, \ldots, b_m$$$ will contain at least $$$k$$$ indices $$$i$$$ such that $$$b_i = i$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of two consecutive lines. The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2000$$$). The second line contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). The numbers in the sequence are not necessarily different.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2000$$$.

Output format:
For each test case output in a single line:

- $$$-1$$$ if there's no desired move sequence;
- otherwise, the integer $$$x$$$ ($$$0 \le x \le n$$$) — the minimum number of the moves to be made so that the resulting sequence will contain at least $$$k$$$ elements that are equal to their indices.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case the sequence doesn't satisfy the desired condition, but it can be provided by deleting the first element, hence the sequence will be $$$[1, 2, 3, 4, 5, 6]$$$ and $$$6$$$ elements will be equal to their indices.

In the second test case there are two ways to get the desired result in $$$2$$$ moves: the first one is to delete the $$$1$$$-st and the $$$3$$$-rd elements so that the sequence will be $$$[1, 2, 3]$$$ and have $$$3$$$ elements equal to their indices; the second way is to delete the $$$2$$$-nd and the $$$3$$$-rd elements to get the sequence $$$[5, 2, 3]$$$ with $$$2$$$ desired elements.

Example input:
4
7 6
1 1 2 3 4 5 6
5 2
5 1 3 2 3
5 2
5 5 5 5 4
8 4
1 2 3 3 2 2 5 5

Example output:
1
2
-1
2

Editorial:
Let's use the concept of dynamic programming. Let's create an array $$$dp$$$ ($$$0$$$-indexed) with size of $$$(n + 1) \times (n + 1)$$$. $$$dp[i][j]$$$ will contain the maximal number of the elements equal to their indices if we have considered the first $$$i$$$ elements of the sequence $$$a$$$ and have not deleted $$$j$$$ elements.
Let's fill the array with zeroes, then we will increase the elements of the array for different $$$i$$$ and $$$j$$$. Let's start the $$$for$$$-loop with parameter $$$i$$$ from $$$0$$$ to $$$n - 1$$$ and the internal one with parameter $$$j$$$ from $$$0$$$ to $$$i$$$. Consider an element $$$a_{i + 1}$$$. We can delete or not delete it.
If we delete this element, the number of the elements equal to their indices will not be increased and the number of the non-deleted element will not be increased, too. It means that the answer for $$$dp[i + 1][j]$$$ may be updated with $$$dp[i][j]$$$. Since we are interested in a maximum answer, we rewrite $$$dp[i + 1][j]$$$ only if $$$dp[i][j]$$$ is greater than $$$dp[i + 1][j]$$$.
Suppose we don't delete this element. We haven't deleted previously $$$j$$$ elements so $$$a_{i + 1}$$$ will have the index $$$(j + 1)$$$ and there will be $$$j + 1$$$ non-deleted elements if we consider $$$i + 1$$$ elements so we must update $$$dp[i + 1][j + 1]$$$. If $$$a_{i + 1} = j + 1$$$ (i. e. an element equal to its index is found), let's update $$$dp[i + 1][j + 1]$$$ with $$$dp[i][j] + 1$$$. Otherwise, we should update it with $$$dp[i][j]$$$. Remember that update may be done only if we rewrite the less value with the greater value.
Let's build the answer as follows. We need to minimize the number of deleted elements (maximize the number of non-deleted elements) so that the number of the elements equal to their indices is at least $$$k$$$. Consider only the elements of $$$dp$$$ having the first index $$$i = n$$$. Let's start a $$$for$$$-loop in the descending order of $$$j$$$. If $$$dp[n][j] \ge k$$$, $$$j$$$ is the maximum number of elements that we will not delete, so the answer is $$$n - j$$$. If we will not find $$$j$$$ such that $$$dp[n][j] \ge k$$$, there's no desired sequence of moves so the answer is $$$-1$$$.
The algorithm works in $$$O(n^2)$$$.