Kanade's sum

Give you an array $A[1..n] $of length $n$.

Let $f(l,r,k)$ be the k-th largest element of $A[l..r]$.

Specially , $f(l,r,k)=0$ if $r-l+1<k$.

Give you $k$ , you need to calculate $\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r,k)$

There are T test cases.

$1\leq T\leq 10$

$k\leq min(n,80)$

$A[1..n] ~is~a~permutation~of~[1..n]$

$\sum n\leq 5*10^5$

There is only one integer T on first line.

For each test case,there are only two integers $n$,$k$ on first line,and the second line consists of $n$ integers which means the array $A[1..n]$

For each test case,output an integer, which means the answer.

1

5 2

1 2 3 4 5

30

2017 Multi-University Training Contest - Team 3