4.4 Ayaan's Group of Study
Ayaan is forming a study group of students. There are n students, each with a skill level a[i].
He wants to select a sequence of students such that:
Each selected student comes after the previous one in the original order (subsequence).
The skill levels are strictly increasing.
The gap between consecutive students is at most k positions in the original list.
Ayaan wants to make the group as large as possible.
Find the maximum number of students he can include in his group.
Constraints
(1 ≤ t ≤ 10)
(1 ≤ n ≤ 2·10⁵, sum of all n across tests ≤ 2·10⁵)
(1 ≤ ai ≤ 10⁹)
Input Format
t — number of test cases
For each test case:
n k — number of students and maximum allowed gap
a1 a2 … an — skill scores
Output Format
For each test case, output the maximum number of students that can be chosen.
Example 1
Input:
2
5 2
2 4 3 5 6
6 3
10 20 15 25 30 5
Output:
4
4
Explanation:
Case 1: One possible circle is [2, 4, 5, 6]. Each step respects the gap ≤ 2 and skills increase.
Case 2: One possible circle is [10, 15, 25, 30].
Log In to solve the Question