← 返回题目列表

AtCoder · abc444_e

H. 稀疏范围

中文机器翻译题面 查看原题

分数: 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