All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Rjit being fond of traveling, needs some leaves from his office for the same. Once in his office, the Monk claimed that no one can split the given array of N elements into less than or equal to K \(Special \; Subsequences\). Being greedy for leaves, Rjit accepted his challenge.

In case Rjit succeeds in the challenge, and let's say he found X \(Sepecial \; Subsequences\) in the array, then he will get \(K-X\) number of leaves.

\(Special \; Subsequences\) should follow the conditions mentioned below:

• The Subsequence should be in decreasing order.
• The adjacent elements should have difference exactly equal to 1.

Help Rjit to maximize the number of leaves. In case Rjit fails in Monk's challenge, print 1.

Note: We consider a splitting of the array to be valid, if each element of the array occurs in exactly one \(Special \;Subsequence\) present in the split.

Input format:
The first line contains T, the number of test cases. For each test case, two integers N and K will be given. Following that line, the next line contains N space separated integers denoting array elements \(A_i\) of array A.

Output format:
You've to print 1, if Rjit fails in Monk's challenge, else print the maximum leaves he can get.

Constraints:
1 ≤ T ≤ \(10\)
1 ≤ N ≤ \(10^5\)
1 ≤ K ≤ \(10^5\)
1 ≤ A_i ≤ \(10^9\)

Sample Input-0:
1
4 1
4 3 2 1

Sample output-0:
0

Sample explanation-0:
Here Rjit will find 1 \(Special \; Subsequence\) that is \(4,3,2,1\). So number of leaves he will get is \(K-1 = 1-1 = 0\).