New Array Subarray Solution

New Array Subarray

PrepBuddy gave you an array of length NN: A1,A2,..,ANA1,A2,..,AN. And, this array is composed of integers between 11 to MM. Construct a new array of length NN: A′1,A′2,..,A′NA1′,A2′,..,AN′, such that:

  • New array A′A′ has integers between 1 to MM.
  • The number of i where Ai!=A′iAi!=Ai′ is not more than KK.
  • XX is defined as the length of the longest subarray of A′A′ where all of its elements are identical, and XX is as small as possible.

As an example, array [1,1,2,2,2,1,3,1][1,1,2,2,2,1,3,1] has [2,2,2][2,2,2] as the longest subarray where all of its elements are identical with length XX = 3.

Your task is to calculate the minimum possible value of XX for the constructed array A′A′. You have to answer for TT independent test cases.

Note: Use of fast IO is recommended as input files are large.

Input Format

The first line contains an integer TT, representing the number of test cases. TT test cases follow. The first line of each test case contains three space-separated integers NN, MM and KK i.e., NN is the length of the array, MM is the range of values of the array and KK is the maximum number of the index where values can be distinct between AA and A′A′. The second line of each test case contains NN space-separated integers (A1,A2…,AN)(A1,A2…,AN). It is guaranteed that integers are positive and between 11 to MM for each test case.

Output Format

For each test case, print the minimum possible value of XX, in the new line.


1≤T≤1021≤T≤102 1≤N,M≤1051≤N,M≤105 0≤K≤N0≤K≤N 1≤Ai≤M1≤Ai≤M The Sum of NN over all test cases doesn’t exceed 106106.

Time Limit

1.5 second


Sample Input

2 8 3 0 1 1 2 2 2 1 3 1 8 3 1 1 1 2 2 2 1 3 1

Sample Output

3 2

Sample test case explanation

In the first test case, since KK = 0, A’ = {1, 1, 2, 2, 2, 1, 3, 1} same as A and X is 3 for {2, 2, 2}. In the second test case, KK = 1, A’ = {1, 1, 2, 1, 2, 1, 3, 1} and X is 2 for {1, 1}.

Note : Please click on 1 or 2 ads to help us run this site and encourages us to provide you the solutions.


Leave a Comment

one + seventeen =