A collector is traveling through a valley of crystals. The valley is represented by an array of N integers, where each integer represents the "type" of crystal found at that position.
The collector has a small bag that can only hold up to K distinct types of crystals at once. The collector wants to pick a continuous segment of the valley to walk through and collect as many crystals as possible, provided the number of unique types in that segment does not exceed K.
What is the maximum number of crystals the collector can collect in a single continuous segment?
The first line contains an integer T, the number of test cases.
For each test case:
The first line contains two integers: N (number of crystals) and K (max distinct types).
The second line contains N space-separated integers representing the types of crystals.
For each test case, output a single integer: the length of the longest contiguous subarray with at most K distinct elements.
1 ≤ T ≤ 50
1 ≤ N ≤ 100000
1 ≤ K ≤ N
0 ≤ Crystal Type ≤ 1000000
The sum of N over all test cases does not exceed 3 × 100000 (i.e., 300000).
| Example Input | Example Output |
|---|---|
2 5 2 1 2 1 2 3 6 3 1 2 1 3 4 2 |
4 4 |
Test Case 1: N = 5, K = 2 Types: [1, 2, 1, 2, 3]
The segment [1, 2, 1, 2] contains 2 distinct types (1 and 2). Length = 4.
If we include the next crystal (type 3), the segment would contain 3 distinct types, which exceeds K = 2.
Maximum length = 4.
Test Case 2: N = 6, K = 3 Types: [1, 2, 1, 3, 4, 2]
The segment [1, 2, 1, 3] contains 3 distinct types (1, 2, 3). Length = 4.
Segment [3, 4, 2] has 3 types. Length = 3.
Max length = 4.