Fixed Points solution codeforces
Consider a sequence of integers. 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 position, so there are no empty spaces in the sequence. So after you make a move, the sequence’s length decreases by . The indices of the elements after the move are recalculated.
E. g. let the sequence be. Let’s select the element in a move. Then after the move the sequence will be equal to , so the -rd element of the new sequence will be and the -th element will be .
You are given a sequence at least elements that are equal to their indices, i. e. the resulting sequence will contain at least indices such that .and a number . You need to find the minimum number of moves you have to make so that in the resulting sequence there will be
The first line contains one integer( ) — the number of test cases. Then test cases follow.
Each test case consists of two consecutive lines. The first line contains two integersand ( ). The second line contains a sequence of integers ( ). The numbers in the sequence are not necessarily different.
It is guaranteed that the sum ofover all test cases doesn’t exceed .
For each test case output in a single line:
- if there’s no desired move sequence;
- otherwise, the integer ( ) — the minimum number of the moves to be made so that the resulting sequence will contain at least elements that are equal to their indices.
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
1 2 -1 2
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 beand elements will be equal to their indices.
In the second test case there are two ways to get the desired result inmoves: the first one is to delete the -st and the -rd elements so that the sequence will be and have elements equal to their indices; the second way is to delete the -nd and the -rd elements to get the sequence with desired elements.