分数: 1800 点
问题陈述
对于序列 S 正整数和正整数 k 和 l, S 据说属于 级别 (k,l) 当满足以下条件之一时:
- 的长度 S is 1,其唯一元素是 k.
- 存在序列 T_1,T_2,...,T_m (m \geq l) 属于级别 (k-1,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
输出
打印子序列的数量 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) 属于级别 (2,3),所以序列 (2,1,1,1,1,1,1) 属于级别 (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