Increasing segments#11790
You are given an array of length and an integer . You can remove any number of elements from the array (possibly zero). What is the minimal number of elements needed to remove from the array, so that in the final array there is no simple subarray of length .
An array of length is called simple if its elements are strictly increasing. Formally, b_i < b_{i+1} for all 1 \le i < m.
Note that k \ge 3.
A subarray of an array is a contiguous segment of . Formally, an array is a subarray of if there exist indices and such that 1 \le l \le r \le n and b = (a_l, a_{l+1}, \ldots, a_r).
Consider the array a = (3, 1, 4, 1, 5, 9, 2). (3,1,4), (1,4,1,5) , are subarrays of (from index to , to and to respectively). (3,1,5) is not a subarray, since the elements are not contiguous.
The first line contains an integer (1 \le t \le 10^5) — the number of cases in one input file.
Each case is described in two lines. The first line contains integers (3 \le k \le n \le 2 \cdot 10^5).
The second line contains integers a_1, a_2, \ldots, a_n (0 \le a_i \le 10^9).
It is guaranteed that sum of over all cases doesn't exceed 2 \cdot 10^5.
For each case, output the minimal number of elements needed to remove from the array, so that in the final array there is no simple subarray of length .
Example 1
In the first test case, we can remove the st and nd elements from the array, resulting in [3,4,5]. There is no simple subarray of length . It can be shown that this is the best possible solution.
In the second test case, we can remove the nd and th elements from the array, resulting in [1,3,3,5]. There is no simple subarray of length . It can be shown that this is the best possible solution.
In the third test case, there is already no simple subarray of length .
( points): n=3;
( points): n=k;
( points): 0 \le a_i < k;
( points): a_i < 10;
( points): n \le 1000;
( points): no additional constraints;