[AGC037F] Counting of Subarrays

## 题目描述 对于一个由正整数组成的序列 $ S $ 和两个正整数 $ k,l $ ，只要 $ S $ 满足下列两个条件之一，我们就称 $ S $ 属于级别 $ (k,l) $ **（一个序列可能同时属于多个级别）**: - $ |S|=1 $且 $ S $ 中唯一的数字是 $ k $ 。 - $ S $ 可以由 $ m $ 个属于级别 $ (k-1,l) $ 的序列 $ T_1,T_2,\dots,T_m(m\ge l) $ 按顺序拼接而得到。 注意到当 $ k=1 $ 时第二个条件是无效的，所以，只有在满足第一个条件时，序列才可能属于级别 $ (1,l) $。 现在你有一个正整数序列 $ A_1,A_2,\dots,A_N $ 和一个正整数 $ L $ ,求满足以下条件的连续子序列 $ A_i,A_{i+1},\dots,A_j(1\le i\le j\le N) $ 的数量： - 存在一个正整数 $ K $ ，使得序列 $ A_i,A_{i+1},\dots,A_j(1\le i\le j\le N) $ 属于级别 $ (K,L) $ 。

[problemUrl]: https://atcoder.jp/contests/agc037/tasks/agc037_f 正整数列 $ S $ 及び正整数 $ k,l $ が以下のいずれかの条件をみたすとき、 $ S $ が **レベル** $ (k,l) $ に属すると定義することにします。 - $ S $ の要素数が $ 1 $ であり、その要素の値が $ k $ である。 - あるレベル$ (k-1,l) $ に属する数列 $ T_1,T_2,...,T_m $ ($ m\ ≧\ 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\ ≦\ i\ ≦\ j\ ≦\ N $) の個数を求めてください。 - ある正整数 $ K $ が存在して、数列 $ A_i,A_{i+1},...,A_j $ がレベル$ (K,L) $に属する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ L $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

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

9 3
2 1 1 1 1 1 1 2 3

22

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

### 制約 - $ 1\ ≦\ N\ ≦\ 2\ \times\ 10^5 $ - $ 2\ ≦\ L\ ≦\ N $ - $ 1\ ≦\ A_i\ ≦\ 10^9 $ ### Sample Explanation 1 例えば $ (1,1,1) $ と $ (2) $ という数列はともにレベル $ (2,3) $ に属するので、$ (2,1,1,1,1,1,1) $ という数列はレベル $ (3,3) $ に属します。