← 返回题目列表

Codeforces · 251/A

A. 线上的点

中文机器翻译题面 查看原题

小Petya非常喜欢积分。最近,他妈妈给了他 OX 线上的 n 个点。现在 Petya 想知道有多少种方法可以选择三个不同的点,使得其中最远的两个点之间的距离不超过 d。

请注意,三个选定点组内的点的顺序并不重要。

输入

第一行包含两个整数:n 和 d (1 ≤ n ≤ 105; 1 ≤ d ≤ 109)。下一行包含n个整数x1,x2,...,xn,它们的绝对值不超过109——Petya得到的点的x坐标。

保证输入中点的坐标严格增加。

输出

打印一个整数 — 三点组的数量,其中两个最远点之间的距离不超过 d。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #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

注意

在第一个样本中,任何三点组都满足我们的条件。

在秒样本中,只有 2 组三个点满足我们的条件:{-3, -2, -1} 和 {-2, -1, 0}。

在第三个样本中,只有一组这样做:{1, 10, 20}。