← 返回题目列表

AtCoder · bitflyer2018_qual_c

C. 徒歩圏内

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

配点 : 400 点

問題文

N 个城市, 它的编号为1, 2, ..., N 。 这些城市按照这个顺序排列。 每个 i (1 \leq i \leq N) 关于城市 i 的坐标是 X_i 。

高桥君是一座城市 i 和城市 如下选择 j 之间的交通方式。

  • 都市 i 和城市 如下选择 j 距离 |X_i - X_j| 的 D 如果低于,请步行。
  • 否则,乘坐火车旅行。

3 一对(数量)城市 找出满足以下条件的 (i, j, k) 的数量。

  • i < j < k
  • 高桥君是一座城市 i 和城市 如下选择 j 和 城市之间。 步行在 j 和城市 如下选择 k 之间移动。 乘坐火车在
  • 高桥君是一座城市 i 和城市 如下选择 k 之间旅行。

制約

  • 3 \leq N \leq 10^5
  • 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • X_i < X_{i + 1} (1 \leq i < N)
  • 0 \leq D \leq 10^9

入力

输入是按以下格式从标准输入给出的。

N D
X_1 X_2 ... X_N

出力

打印答案。


入力例 1

5 7
11 13 17 19 23

出力例 1

5

满足条件 集合 (i, j, k) 是 有 (1, 2, 4), (1, 3, 4), (1, 3, 5), (2, 3, 5), (2, 4, 5) 的 合并 5 件。


入力例 2

4 10
0 3 6 10

出力例 2

0

入力例 3

6 36
0 5 32 48 69 71

出力例 3

4

入力例 4

6 405885562
133510576 158828561 245133494 461153833 840383806 867039395

出力例 4

6