You will be given an array A of length N and two more integers K and X. You have to find the length of the largest interesting sub-array inside the array A.
A sub-array is called interesting if the following two conditions are satisfied.
- The largest element in that sub-array is K.
- The number of occurrences of K in that sub-array is at least X.
Find the maximum length of a sub-array which is called interesting.
Input
The first line of the input contains a single integer T which denotes the number of test cases. The first line of a test case contains three integers N, K and X. The next line of the test case contains N space separated integers denoting the elements of the array A.
Constraints
${1 \leq T \leq 10}$${1 \leq N \leq 50000}$${1 \leq X \leq N}$${1 \leq A_{i}, K \leq 1000000}$
Output
For each of the test cases, print the result in a single line. If there's no valid interesting sub-array then print -1.
Sample
| Input | Output |
|---|---|
2 8 6 2 6 2 6 3 8 2 1 6 12 6 2 6 2 6 8 2 1 6 6 4 6 9 3 | 4 6 |
In the first test case of the sample I/O, the largest interesting sub-array starts at index 1 and ends at index 4 (1 based indexing). In this sub-array, 6 occurs 2 times (which is >= X) and 6 is the largest element, so it's an interesting sub-array. No other interesting sub-array has length greater than 4.
