分数: 450 点
问题陈述
给你一个长度的整数序列 N, (A_1,\dots,A_N),和一个正整数 D.
查找整数对的数量 (L,R) 满足以下两个条件:
- 1 \leq L \leq R \leq N
- 的任意两个元素 (A_L,A_{L+1},\dots,A_R) 至少有差异 D.
- 也就是说, |A_i-A_j|\geq D 对于所有整数对 (i,j) 满意 L \leq i < j \leq R.
约束
- 2\leq N \leq 4\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq D \leq 10^9
输入
输入由标准输入按以下格式给出:
N D A_1 \dots A_N
输出
输出答案。
示例输入 1
5 3 3 1 4 1 5
示例输出 1
8
八对 (1,1),(2,2),(3,3),(4,4),(5,5),(2,3),(3,4),(4,5) 满足条件。
示例输入 2
9 1 1 2 3 4 5 6 7 8 9
示例输出 2
45
示例输入 3
6 1000000000 123456789 234567891 987654321 321987654 1000000000 1
示例输出 3
6