配点 : $1800$ 点

問題文

正整数列 $S$ 及び正整数 $k,l$ が以下のいずれかの条件をみたすとき、 $S$ が レベル $(k,l)$ に属すると定義することにします。

• $S$ の要素数が $1$ であり、その要素の値が $k$ である。
• あるレベル$(k-1,l)$ に属する数列 $T_1,T_2,...,T_m$ ($m \geq l$) が存在して、 $T_1,T_2,...,T_m$ をこの順に連結して得られる数列と $S$ が一致する。

ただし、$k=1$ のとき二番目の条件は意味を持たない、つまりレベル$(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$ がレベル$(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$

出力

条件をみたす部分列の個数を出力せよ。

9 3
2 1 1 1 1 1 1 2 3

22

例えば $(1,1,1)$ と $(2)$ という数列はともにレベル $(2,3)$ に属するので、$(2,1,1,1,1,1,1)$ という数列はレベル $(3,3)$ に属します。

9 2
2 1 1 1 1 1 1 2 3

41

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

31