• # For Solution

You are given a sequence of integers A1,A2,,ANA1,A2,…,AN and an integer KK. Find the number of contiguous subsequences AL,AL+1,,ARAL,AL+1,…,AR such that RL+1KR−L+1≥K and the KK-th element of the subsequence (AL+K1AL+K−1) is equal to the maximum of all elements of the entire sequence.

### Input Format K-th Maximum solution codechef

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains two space-separated integers NN and KK.
• The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

### Output Format

For each test case, print a single line containing one integer — the number of contiguous subsequences satisfying the given conditions.

### Constraints K-th Maximum solution codechef

• 1T2001≤T≤200
• 1KN21051≤K≤N≤2⋅105
• |Ai|105|Ai|≤105 for each valid ii
• the sum of NN over all test cases does not exceed 51055⋅105

• T10T≤10
• N100N≤100

Subtask #2 (90 points) original constraints

### Sample Input 1  K-th Maximum solution codechef

1
5 3
1 2 3 4 5


### Sample Output 1

1


### Explanation K-th Maximum solution codechef

Example case 1: (3,4,5)(3,4,5) is the only contiguous subsequence such that its 33-rd element is equal to the maximum of the whole sequence (which is 55).