K-th Largest Query

Problem Description

Given a permutation $a_1, a_2, a_3, \dots, a_n$ of $1 \sim n$, consider all intervals $[l, r]$ satisfying $r - l + 1 \ge k$. For each such interval, take the $k$-th largest element among the numbers inside it, and output the sum of all these $k$-th largest elements.

Input Format

The first line contains two integers $n, k$.

The next line contains $n$ integers $a_1, a_2, a_3, \dots, a_n$.

Output Format

Output one line containing a single integer: the answer.

Sample Input

5 2
1 2 3 4 5

Sample Output

30

Sample Explanation

The intervals $[1,5], [2,5], [3,5], [4,5]$ have $4$ as their $2$nd largest; the intervals $[1,4], [2,4], [3,4]$ have $3$ as their $2$nd largest; the intervals $[1,3], [2,3]$ have $2$ as their $2$nd largest; the interval $[1,2]$ has $1$ as its $2$nd largest.

Constraints

There are $10$ test cases in total.

• Test points $1, 2$: $1 \le n \le 100$.
• Test points $3, 4$: $1 \le n \le 10^3$.
• Test points $5, 6$: $k = 1$.
• Test points $7, 8$: $n \le 5 \times 10^4$.
• For $100\%$ of the data: $1 \le n \le 5 \times 10^5,\ 1 \le k \le 50$.

Hint

See the files attached to this problem.