NanoApe Loves Sequence Ⅱ

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 262144/131072 K (Java/Others)

Description

NanoApe, the Retired Dog, has returned back to prepare for for the National Higher Education Entrance Examination!

In math class, NanoApe picked up sequences once again. He wrote down a sequence with $n$ numbers and a number $m$ on the paper.

Now he wants to know the number of continous subsequences of the sequence in such a manner that the $k$-th largest number in the subsequence is no less than $m$.

Note : The length of the subsequence must be no less than $k$.

Input

The first line of the input contains an integer $T$, denoting the number of test cases.

In each test case, the first line of the input contains three integers $n,m,k$.

The second line of the input contains $n$ integers $A_1, A_2, ..., A_n$, denoting the elements of the sequence.

$1 \le T \le 10,~2 \le n \le 200000,~1 \le k \le n/2,~1 \le m,A_i \le 10^9$

Output

For each test case, print a line with one integer, denoting the answer.

Sample Input

1 7 4 2 4 2 7 7 6 5 1

Sample Output

18

Hint

wange2014

Source

BestCoder Round #86

提交代码