M. G. 第K大和

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

G. 第K大和

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

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

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

\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r, k)

输入包含多组数据。

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

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

输入

1
5 2
1 2 3 4 5

输出