Largest Sum Subarray with At Most K Distinct Numbers

You are given an array of integers and a positive integer (K). Your task is to find a contiguous subarray that contains at most (K) distinct integers and has the maximum possible sum. If there are multiple contiguous subarrays achieving the maximum sum, you must return the length of the smallest such subarray.

For example, consider the array [1, 2, 1, 2, 3] with (K = 2). The subarray [1, 2, 1, 2] has at most 2 distinct integers and sums to 6. In this case, the answer would be 4 (the length of the subarray) if no other subarray yields a higher sum or the same sum with a shorter length.

The input is read from standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The first line of input contains a single integer (T) denoting the number of test cases. Each test case is described as follows:

• The first line of each test case contains two integers (N) and (K), where (N) is the number of elements in the array, and (K) is the maximum number of distinct integers allowed in the subarray.
• The second line contains (N) space-separated integers representing the elements of the array.

For example:

3 5 2 1 2 1 2 3 6 3 1 2 1 3 4 3 4 2 1 2 3 4

outputFormat

For each test case, output a single integer on a new line: the length of the smallest contiguous subarray that has the maximum sum among all subarrays which contain at most (K) distinct integers.## sample

3
5 2
1 2 1 2 3
6 3
1 2 1 3 4 3
4 2
1 2 3 4

4
4
2