Problem G: [Bonus] K-th Largest Elements

Problem G: [Bonus] K-th Largest Elements

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 641  Solved: 88
[Submit][Status][Web Board]

Description

There is an array $$a[ 1... n ]$$, which has $$n$$ integers.

Consider all the consecutive intervals of $$a[ ]$$ which have at least $$K$$ integers. We find the $$K$$-th largest element from each of such intervals, and add these elements into an array $$B$$ which is initially empty. Notice that the same element can be added for multiple times. Obviously, finally the length of $$B$$ is $$\frac{(n+2-K)(n+1-K)}{2}$$.

For example, $$a=[4,5,5,8,6]$$ and $$K=4$$. Then the consecutive intervals with at least $$K=4$$ integers are $$[4,5,5,8], [5,5,8,6], [4,5,5,8,6]$$. After finding the $$K$$-th largest elements, we get $$B=[4,5,5]$$.

Do you know what is the $$M$$-th largest integer in array $$B[ ]$$?

Input

The first line contains an integer $$T(1\leq T\leq 5)$$, indicating the number of test cases.

For each test case, the first line contains three integers $$n(1\leq n\leq 10^5), K(1\leq K\leq n), M(1\leq M\leq \frac{(n+2-K)(n+1-K)}{2} )$$. The second line contains $$n$$ integers $$a[i] (1\leq a[i]\leq 10^9)$$.

Output

For each test case, output the answer in one line.

Sample Input

1
5 4 1
4 5 5 8 6

Sample Output

5

[Submit][Status]