题目描述

给定一个正整数序列 $S$ 和正整数 $k$、$l$，如果满足以下条件之一，则称 $S$ 属于 level $(k,l)$：

• $S$ 的长度为 $1$，并且唯一的元素为 $k$。
• 存在属于 level $(k-1,l)$ 的序列 $T_1,T_2,...,T_m$（$m \geq l$），使得按照 $T_1,T_2,...,T_m$ 的顺序连接得到的字符串与 $S$ 相等。

注意当 $k=1$ 时，第二个条件无效，也就是说，只有满足第一个条件的序列才属于 level $(1,l)$。

给定正整数序列 $A_1,A_2,...,A_N$ 和正整数 $L$。请找出满足以下条件的子序列 $A_i,A_{i+1},...,A_j$（$1 \leq i \leq j \leq N$）的个数：

• 存在正整数 $K$，使得序列 $A_i,A_{i+1},...,A_j$ 属于 level $(K,L)$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $2 \leq L \leq N$
• $1 \leq A_i \leq 10^9$

输入

输入通过标准输入给出，格式如下：

$N$ $L$ $A_1$ $A_2$ $...$ $A_N$

输出

打印出满足条件的子序列 $A_i,A_{i+1},...,A_j$（$1 \leq i \leq j \leq N$）的个数。

示例输入 1

9 3
2 1 1 1 1 1 1 2 3

示例输出 1

22

例如，序列 $(1,1,1)$ 和 $(2)$ 都属于 level $(2,3)$，因此序列 $(2,1,1,1,1,1,1)$ 属于 level $(3,3)$。

示例输入 2

9 2
2 1 1 1 1 1 1 2 3

示例输出 2

41

示例输入 3

15 3
4 3 2 1 1 1 2 3 2 2 1 1 1 2 2

示例输出 3

31