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 翻译