Significant inversions
Easy
Execution time limit is 0.5 seconds
Runtime memory usage limit is 32 megabytes
Consider an arbitrary sequence of numbers x[1]
, x[2]
, ..., x[n]
. A pair of indices (j, k) is called an inversion (violation of the order), if j < k and x[j]
> x[k]
. For any non-negative integer t a pair of indices (j, k) is called a t-significant inversion, if j < k and x[j]
> x[k]
+ t.
Count the number of t-significant inversions in the sequence x[1]
, x[2]
, ..., x[n]
.
Input
The first line contains two integers n (1 ≤ n ≤ 50000) and t (0 ≤ t ≤ 10^9
). The second line contains integers x[1]
, x[2]
, ..., x[n]
, not greater than 10^9
by absolute value.
Output
Print the number of t-significant inversions in the sequence x[1]
, x[2]
, ..., x[n]
.
Examples
Input #1
Answer #1
Submissions 883
Acceptance rate 30%