codeFlyer (bitFlyer Programming Contest)

C - 徒歩圏内


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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

Submit提出する