Kanade's sum

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

Memory Limit: 65536/65536 K (Java/Others)

Description

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$

Input

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]$

Output

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

Sample Input

1 5 2 1 2 3 4 5

Sample Output

30

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码