Problem
ぺチャちゃんはドットが大好き。最近、彼の母親は OX ライン上にある n ポイントを彼に与えました。 Petya は、選択した 2 つのポイントの最も遠い 2 つのポイント間の距離が d を超えないように、3 つの異なるポイントを選択する方法は何通りあるのだろうかと考えました。
選択したトリオ内のポイントの順序は重要ではないことに注意してください。
入力
最初の行には 2 つの整数が含まれています: n と d (1 ≤ n ≤ 105; 1 ≤ d ≤ 10< sup>9)。次の行には、109 を超えないモジュロ x1、 x2、 ...、 xn の n 個の整数が含まれます — Petya に与えられたポイントの x 座標。
入力の点の座標が厳密に増加することが保証されています.
出力
単一の整数を表示 —最も遠い 2 つのポイント間の距離が d を超えないポイントのトリプルの数。
C++ で 64 ビットの数値を読み書きするために %lld 指定子を使用しないでください。 cin、cout ストリーム、または %I64d 指定子を使用することをお勧めします。
<本体>
| 入力 |
出力 |
|
4 3
1 2 3 4
|
4 |
|
4 2
-3 -2 -1 0
|
2 |
|
5 19
1 10 20 30 50
|
1 |
最初の例では、任意の 3 つの異なるポイントが適切です。
2 番目の例では、適切なトリプルは {-3, -2, -1} と {-2, -1, 0} の 2 つだけです。
3 番目の例では、{1, 10, 20} という 1 つのトリプルが適合します。