Problem
Der kleine Petya liebt Punkte sehr. Kürzlich schenkte ihm seine Mutter n Punkte, die auf einer geraden OX lagen. Pete hat sich gefragt, wie er drei verschiedene Punkte auswählen kann, so dass der Abstand zwischen den beiden am weitesten entfernten Punkten der ausgewählten Punkte d nicht überschreitet.
Beachten Sie, dass die Reihenfolge der Punkte innerhalb des ausgewählten Dreiecks keinen Wert hat.
Eingabe
Die erste Zeile enthält zwei ganze Zahlen: n und d (1 ≤ n ≤ 105; 1 ≤ d ≤ 109). Die nächste Zeile enthält n Ganzzahlen x1, x2, .... xn, die modulo 109 nicht übertreffen,— x sind die Koordinaten der Punkte, die Pete geschenkt hat.
Es wird garantiert, dass die Koordinaten der Punkte in den Eingabedaten stark ansteigen.
Ausgabe
Geben Sie eine einzelne ganze Zahl aus, — die Anzahl der drei Punkte, bei denen der Abstand zwischen den beiden am weitesten entfernten Punkten d nicht übersteigt.
Bitte verwenden Sie den %lld-Spezifizierer nicht, um 64-Bit-Zahlen in C++ zu lesen oder zu schreiben. Es wird empfohlen, cin-, Cout- oder %I64d-Threads zu verwenden.
| Eingabe |
Ausgabe |
|
4 3
1 2 3 4
|
4 |
|
4 2
-3 -2 -1 0
|
2 |
|
5 19
1 10 20 30 50
|
1 |
Im ersten Beispiel sind drei verschiedene Punkte für uns geeignet.
Im zweiten Beispiel sind für uns nur zwei Dreiergruppen geeignet: {-3, -2, -1} und {-2, -1, 0}.
Im dritten Beispiel passt uns ein Dreier: {1, 10, 20}.