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.

限制

• 时间限制：$2s$
• 空间限制：$256M$

题目描述

你对数组的神秘魔力充满了好奇心。在你的昔日旅途中，你听说了一个关于数组的传说：每个数组都隐藏着一种神秘的力量，只要数组的最大值出现的次数大于等于某个阈值$k$，这个数组便会拥有$1$的“魔力值”，否则不拥有魔力值；而一个数组的“魔力等级”，是其所有子数组的魔力值之和。

现今给定一个长度为$n$的数组，你迫切地想知道这个数组的魔力等级是多少。

请回忆：子数组是指原数组中连续的一段元素组成的数组片段。例如，对于数组$a=[3,2,1,3,2]$，易知$[2,1]$，$[1,3]$，$[3,2,1]$都是其子数组，但是$[3,3]$，$[1,4]$不是其子数组。

输入格式

第一行包含两个整数$n$和$k$ $1 \le k \le n \le 10^6$ ，分别表示数组长度和阈值 第二行包含$n$个整数 $a_1,a_2, \ldots ,a_n (1 \le a_i \le n)$，表示给定数组

输出格式

在一行内输出一个整数，即给定数组的魔力等级。

样例

输入

5 2
1 3 3 2 2

输出

7

样例解释

在第一个样例中，子数组$[1,3,3]$，$[1,3,3,2]$，$[1,3,3,2,2]$，$[3,3]$，$[3,3,2]$，$[3,3,2,2]$，$[2,2]$的最大值出现次数不小于$2$次，共有$7$个魔力值为$1$的子数组，因此，数组的魔力等级为$7$。

数据分布

$40\%$ 的样例，$1 \le k \le n \le 100$

$100\%$ 的样例， $1 \le k \le n \le 10^6$ ，$a_1,a_2, \ldots ,a_n (1 \le a_i \le n)$