Little Petya likes points a lot. Recently his mom has presented him n points lying on the line OX . Now Petya is wondering in how many ways he can choose three distinct points so that the distance between the two farthest of them doesn't exceed d . Note that the order of the points inside the group of three chosen points doesn't matter.
输入描述:
The first line contains two integers: n and d (1 ≤ n ≤ 105; 1 ≤ d ≤ 109). The next line contains n integers x1, x2, ..., xn, their absolute value doesn't exceed 109 — the x-coordinates of the points that Petya has got.It is guaranteed that the coordinates of the points in the input strictly increase.
输出描述:
Print a single integer — the number of groups of three points, where the distance between two farthest points doesn't exceed d.Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
示例1
输入
4 3<br />1 2 3 4<br />4 2<br />-3 -2 -1 0<br />5 19<br />1 10 20 30 50<br />
备注:
In the first sample any group of three points meets our conditions.In the seconds sample only 2 groups of three points meet our conditions: {-3, -2, -1} and {-2, -1, 0}.In the third sample only one group does: {1, 10, 20}.
加载中...