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

现在考虑一个包含 $n$ 只鹅和 $k$ 只鸭子的游戏。鹅的编号从 $1$ 到 $n$，第 $i$ 只鹅可以完成编号为 $a_i$ 的任务。鹅决定派遣一个连续区间的鹅去完成任务，这意味着它们会选择两个整数 $l, r$，满足 $1 \le l \le r \le n$，所有编号 $i$ 满足 $l \le i \le r$ 的鹅都将去完成它们的任务。这样的决定被称为一个方案，两个方案被认为是不同的，当且仅当它们选择的区间不同。

鸭子会潜伏在某个任务地点，并杀死所有试图完成该任务的鹅。它们不能选择一个会有超过 $k$ 只鹅到达的任务地点，因为它们无法杀死所有人且会有目击者；它们也不能选择一个会有少于 $k$ 只鹅到达的任务地点，因为它们会误杀自己的队友。换句话说，它们只能选择一个恰好有 $k$ 只鹅到达的任务地点。

如果存在一个鸭子可以埋伏的任务地点，则称该方案是危险的。请帮助鹅计算有多少个方案对鹅来说是不危险的。请注意，鹅不需要通过方案完成所有任务。

输入格式

第一行包含两个整数 $n, k$ ($1 \le n, k \le 10^6$)。

第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ ($1 \le a_i \le 10^6$) 表示编号为 $i$ 的鹅所对应的任务编号。

输出格式

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

样例

输入 1

6 2
1 2 2 1 3 3

输出 1

10

输入 2

6 1
1 2 3 4 5 6

输出 2

0