G. 第K大和

题目描述

给定序列 $A$，$A$ 是 $1$ 到 $n$ 的全排列。

现统计所有子区间的第 $k$ 大值和，特别的，没有第 $k$ 大值的区间贡献为 $0$。

定义 $f(l, r, k)$ 函数为区间 $[l, r]$ 第 $k$ 大的数，如果区间长度 $r-l+1 < k$，则 $f = 0$。 请求解：

输入格式

输入包含多组数据。

对于每组数据，第一行包括两个正整数 $n, k$，第二行包括 $n$ 个整数，表示序列 $A$。

输出格式

对于每组数据，输出一个整数，表示答案。

样例

输入

1
5 2
1 2 3 4 5

输出

30

数据范围与提示

• 数据组数 $case \le 10$
• $k \le \min(n, 80)$
• $\sum n \le 5 \times 10^5$