分数: 600 点
问题陈述
给你一个排列 P=(P_1,\ldots,P_N) of (1,\ldots,N),和一个整数 K.
查找整数对的数量 (L, R) 满足以下所有条件:
-
1 \leq L \leq R \leq N
-
\mathrm{max}(P_L,\ldots,P_R) - \mathrm{min}(P_L,\ldots,P_R) \leq R - L + K
约束
- 1 \leq N \leq 1.4\times 10^5
- P 是一个排列 (1,\ldots,N).
- 0 \leq K \leq 3
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K P_1 P_2 \ldots P_N
输出
打印答案。
示例输入 1
4 1 1 4 2 3
示例输出 1
9
以下九对 (L, R) 满足条件。
- (1,1)
- (1,3)
- (1,4)
- (2,2)
- (2,3)
- (2,4)
- (3,3)
- (3,4)
- (4,4)
对于 (L,R) = (1,2),我们有 \mathrm{max}(A_1,A_2) -\mathrm{min}(A_1,A_2) = 4-1 = 3 和 R-L+K=2-1+1 = 2,不满足条件。
示例输入 2
2 0 2 1
示例输出 2
3
示例输入 3
10 3 3 7 10 1 9 5 4 8 6 2
示例输出 3
37