数据说明

本题有附加文件（大样例）。

题目描述

给定一个 $1$ 到 $n$ 的排列，求对于每个区间 $[l,r]$ 且 $r-l+1 \ge k$ ，其第 $k$ 大的数的和。

输入格式

第一行两个正整数 $n,k$ 。 第二行是 $n$ 个数字，表示给定序列。

输出格式

仅一行，即答案。

样例

5 2
1 2 3 4 5

30

样例1解释

共有 $10$ 个区间的长度大于等于 $2$ ，其中区间 $[1,5]$ ， $[2,5]$ ， $[3,5]$ ， $[4,5]$ 的第二大为 $4$ ，区间 $[1,4]$ ， $[2,4]$ ， $[3,4]$ 的第二大为 $3$ ，区间 $[1,3]$ ， $[2,3]$ 的第二大为 $2$ ，区间 $[1,2]$ 的第二大为 $1$ ，答案即为 $4 \times 4 + 3 \times 3 + 2 \times 2 + 1 \times 1 = 30$ 。

数据范围与约定

• 对于 $100 \%$ 的数据，满足 $1 \le n \le 5 \times 10^5$ ， $1 \le k \le 50$ 。
• 此外，本题数据还满足下表所示：