M. G. 第K大和

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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

输出