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.