Significant inversions
Significant inversions
Consider an arbitrary sequence of numbers x1, x2, ..., xn. A pair of indices (j, k) is called an inversion (violation of the order), if j < k and xj > xk. For any non-negative integer t a pair of indices (j, k) is called a t-_significant inversion_, if j < k and xj > xk + t.
Count the number of t-significant inversions in the sequence x1, x2, ..., xn.
Input
The first line contains two integers n (1 ≤ n ≤ 50000) and t (0 ≤ t ≤ 109). The second line contains integers x1, x2, ..., xn, not greater than 109 by absolute value.
Output
Print the number of t-significant inversions in the sequence x1, x2, ..., xn.
6 0 1 2 2 9 5 4
3
Example description: In sample 1 the inversions are: (4, 5), (4, 6) and (5, 6). They all are 0-significant. In sample 2 the inversions are (3, 4) and (3, 5). But x3 ≤ x5 + 2, inversion (3, 5) is not 2-significant. But pair (3, 4) is so.