Little Petya loves dots. Recently, his mother gave him n points that lie on the line OX. Petya wondered how many ways he can choose three different points so that the distance between the two farthest of the selected points does not exceed d.
Note that the order of the points within the selected trio doesn't matter.
Input
The first line contains two integers: n and d (1 ≤ n ≤ 105; 1 ≤ d ≤ 10< sup>9). The next line contains n integers x1, x2, ..., xn, modulo not exceeding 109 — x-coordinates of points given to Petya.
It is guaranteed that the coordinates of the points in the input are strictly increasing.
Output
Print a single integer — the number of triples of points where the distance between the two farthest points does not exceed d.
Please don't use the %lld specifier to read or write 64-bit numbers in C++. It is recommended to use cin, cout streams or the %I64d specifier.
| Input |
Output |
|
4 3
1 2 3 4
|
4 |
|
4 2
-3 -2 -1 0
|
2 |
|
5 19
1 10 20 30 50
|
1 |
In the first example, any three different points are suitable for us.
In the second example, only 2 triples are suitable for us: {-3, -2, -1} and {-2, -1, 0}.
In the third example, one triple fits us: {1, 10, 20}.