差值不超过 K 的数对

题目描述

给定 n 个整数 a[1..n] 和一个非负整数 K。

请计算有多少对下标 (i, j) 满足：

• 1 <= i < j <= n
• |a[i] - a[j]| <= K

答案可能很大，请使用 long long。

输入格式

第一行输入两个整数 n, K。

第二行输入 n 个整数 a[i]。

输出格式

输出满足条件的数对数量。

样例

输入

5 3
1 5 3 8 4

输出

6

数据范围

• 1 <= n <= 2 * 10^5
• 0 <= K <= 10^9
• 0 <= a[i] <= 10^9

提示

直接枚举所有 (i,j) 是 O(n^2)。当 n = 2 * 10^5 时，需要寻找更快的方法。