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

小田的气球真好看

balloon.in balloon.out

题目描述

有 $n$ 个五颜六色的气球挂成一排。小田觉得，对于每个气球来说，只有它和前一个颜色相同的气球距离不超过 $k$ 才是好看的。（当然，当这个气球前面没有和它颜色相同的气球时，这个气球也算是好看的。）

小田现在需要选择一个区间的气球来布置他的家，所以他需要选择一个完美的区间，即将这个区间里面的每个气球都是好看的。

现在对于这一排气球，小田想知道，有多少个完美的区间。

输入描述

输入包含 $2$ 行。

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

第二行输入 $n$ 个正整数 $c_{i}$，表示第 $i$ 个气球的颜色。

输出描述

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

输入输出样例

输入 #1

4 1
1 0 0 1

输出 #1

9

输入 #2

8 3
1 4 3 2 1 4 1 2

输出 #2

27

说明/提示

【样例 1 解释】

完美区间一共有： $[1], [0], [0], [1], [1,0], [0, 0], [0, 1], [1,0,0], [0,0,1]$

$[1,0,0,1]$ 不是完美区间，因为两个 $1$ 之间的距离大于 $k$。

【数据范围】

对于 $20\%$ 的数据，$n \le 10^2$。

对于另外 $30 \%$ 的数据，$n \le 10^5$，且气球颜色只有 $0$ 和 $1$ 。

对于所有测试数据，有：$1 \le n,k,c_{i} \le 10^{5}$ 。