A13 - Close Pairs Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 1000

問題文

N 個の整数が黒板に書かれています。書かれた整数は小さい順に A_1, A_2, \cdots, A_N です。異なる 2 つの整数のペアを選ぶ方法は全部で N(N-1)/2 通りありますが、その中で差が K 以下であるような選び方は何通りありますか。

制約

  • 1 \leq N \leq 100\,000
  • 1 \leq K \leq 10^9
  • 1 \leq A_1 < A_2 < \cdots < A_N \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N K
A_1 A_2 \cdots A_N

出力

差が K 以下である整数のペアの選び方を一行に出力してください。


入力例 1

7 10
11 12 16 22 27 28 31

出力例 1

11