AT_agc037_f [AGC037F] Counting of Subarrays

定义正整数序列 $S$ 属于**等级** $(k, l)$，当且仅当满足以下任一条件： - $S$ 的元素个数为 $1$，且该元素的值为 $k$。 - 存在属于等级 $(k-1, l)$ 的数列 $T_1, T_2, \ldots, T_m$（$m \geq l$），将 $T_1, T_2, \ldots, T_m$ 按顺序连接后得到的数列与 $S$ 完全一致。 注意，当 $k=1$ 时，第二个条件没有意义，因此等级 $(1, l)$ 的正整数序列只能满足第一个条件。 给定正整数序列 $A_1, A_2, \ldots, A_N$ 和正整数 $L$。请计算满足下述条件的子序列 $A_i, A_{i+1}, \ldots, A_j$（$1 \leq i \leq j \leq N$）的个数： - 存在某个正整数 $K$，使得数列 $A_i, A_{i+1}, \ldots, A_j$ 属于等级 $(K, L)$。

输入从标准输入中按以下格式给出。 > $N$ $L$ $A_1$ $A_2$ $\ldots$ $A_N$

输出满足条件的子序列的个数。

## 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $2 \leq L \leq N$ - $1 \leq A_i \leq 10^9$ ## 样例说明 1 例如，数列 $(1,1,1)$ 和 $(2)$ 都属于等级 $(2,3)$，因此数列 $(2,1,1,1,1,1,1)$ 属于等级 $(3,3)$。 由 ChatGPT 4.1 翻译