← 返回题目
题库练习 Points on Line
← 上一题 下一题 →

A8840 | Points on Line

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

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<=10^{5}; 1<=d<=10^{9}$ ). The next line contains $n$ integers $x_{1},x_{2},...,x_{n}$ , their absolute value doesn't exceed $10^{9}$ — 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
1 2 3 4
输出 #1
4
输入 #2
4 2
-3 -2 -1 0
输出 #2
2
输入 #3
5 19
1 10 20 30 50
输出 #3
1
C++ 编辑器
输入
输出