第k大查询

题目描述

给定一个 $1\sim n$ 的排列 $a_1, a_2, a_3, \dots, a_n$，想知道所有的区间 $[l,r]$ 满足 $r-l+1\geq k$，这样的区间里的数中第 $k$ 大的元素，输出它们的和。

输入格式

第一行一个整数 $n,k$。

接下来一行 $n$ 个整数 $a_1, a_2, a_3, \dots, a_n$。

输出格式

输出一行，一个整数表示答案。

样例输入

5 2
1 2 3 4 5

样例输出

30

样例解释

其中区间$[1,5],[2,5],[3,5],[4,5]$的第2大为$4$，区间$[1,4],[2,4],[3,4]$的第2大为$3$，区间$[1,3],[2,3]$的第2大为$2$，区间$[1,2]$的第2大为$1$。

数据范围

共 $10$ 组数据。

测试点 $1,2$ 满足$1\leq n \leq 100$。

测试点 $3,4$ 满足 $1\leq n \leq 10^3$。

测试点 $5, 6$ 满足 $k=1$。

测试点 $7, 8$ 满足 $n\leq 5\times 10^4$。

对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times 10^5, 1\leq k\leq 50$。

提示

见下发文件。