### 问题描述 你被聘为大型音乐节的音乐策划师。为了给观众提供最佳的音乐体验，你决定制定一套播放规则，确保观众在短时间内体验到各种风格的音乐，而不是同一种风格的重复。为了避免某种风格的音乐在任意时间段内被过度播放，你规定在任何连续的时间段里，同一音乐风格的歌曲不能连续播放超过 $k$ 次。 现在，你收到了一份长达 $n$ 首的歌曲清单，每首歌都有一个与之对应的音乐风格 ID。请你计算，按照你的规定，有多少种可能的连续播放列表？ ### 输入格式 第一行：两个整数 $n$ 和 $k$，$(1 \leq n \leq 10^5, 1 \leq k \leq 10^5)$，分别表示歌曲的数量和同一音乐风格歌曲的最大连续播放次数。 第二行：$n$ 个整数，每个数字代表 $n$ 首歌的音乐风格 ID，$(1 \leq songs[i] \leq 10^5)$。 ### 输出格式 输出一个整数，表示满足规则的连续播放列表的数量。 ### 样例输入 ``` 5 2 1 2 2 3 2 ``` ### 样例输出 ``` 13 ``` ### 样例说明 相同音乐风格的歌曲连续播放不超过 $2$ 次，共有 $13$ 种播放列表是合法的； 长度为 $1$ 的区间 $[1]$、$[2]$、$[2]$、$[3]$、$[2]$ 均满足条件，共 $5$ 种可选择区间； 长度为 $2$ 的区间 $[1,2]$、$[2,2]$、$[2,3]$、$[3,2]$ 均满足条件，共 $4$ 种可选择区间； 长度为 $3$ 的区间 $[1,2,2]$、$[2,2,3]$、$[2,3,2]$ 均满足条件，共 $3$ 种可选择区间； 长度为 $4$ 的区间 $[1,2,2,3]$ 满足条件，共 $1$ 种可选择区间； 对于长度为 $5$ 的区间，超过 $2$ 首的同一音乐风格的歌曲，因此不满足条件。 ### 测评数据规模 对于 $40$% 的数据，$n \leq 10$。 对于 $80$% 的数据，$n \leq 10^3$。 对于 $100$% 的数据，$n \leq 10^5$。