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

C. 鹅鸭杀

题目描述

在游戏鹅鸭杀中，鹅的目标是完成任务并活下来。然而，作为破坏者的鸭子会试图通过杀死鹅来阻止它们完成任务。

现在考虑一个由$n$只鹅和$k$只鸭子组成的游戏。鹅被编号为1到$n$，第$i$只鹅可以完成编号为$a_i$的任务。鹅决定派遣一个鹅的区间来完成任务，这意味着它们会选择两个整数$l$和$r$，满足$1 \leq l \leq r \leq n$，并且所有编号为$i$的鹅满足$l \leq i \leq r$将会去完成他们的任务。这样的决定被称为一个计划，当且仅当区间不同的时候，两个计划被认为是不同的。

不同的任务有不同的位置。鸭子会依次去往每一个任务位置，并杀死所有试图在该位置完成任务的鹅。他们不能选择那些会有大于等于$k$只鹅前来的任务位置，因为无法把该位置的鹅全部杀死。

如果一个计划，鸭子可以杀死所有的鹅，那么一个计划被称为危险的。请帮助鹅计算有多少个计划对鹅来说是危险的。

输入格式

第一行输入两个整数$n, k$

接下来一行输入一个整数$a_1, a_2, \cdots, a_n$

输出格式

输出一个数表示答案

输入样例1

6 2
1 2 2 1 3 3

输出样例1

10

输入样例2

6 1
1 2 3 4 5 6

输出样例1

0

数据范围：

对于30%的数据，$n, k \leq 5000$

对于另外30%数据，$1 \leq a_i \leq 100$

对于100%的数据，$1 \leq n, k \leq 2 \times 10^5, a_i \leq 10^5$