Problem
La petite Petya adore les points. Récemment, sa mère lui a donné n points qui se trouvent sur la ligne OX. Petya s'est demandé de combien de façons il pouvait choisir trois points différents pour que la distance entre les deux points sélectionnés les plus éloignés ne dépasse pas d.
Notez que l'ordre des points dans le trio sélectionné n'a pas d'importance.
Entrée
La première ligne contient deux entiers : n et d (1 ≤ n ≤ 105 ; 1 ≤ d ≤ 10< sup>9). La ligne suivante contient n entiers x1, x2, ..., xn, modulo n'excédant pas 109 — Coordonnées x des points donnés à Petya.
Il est garanti que les coordonnées des points dans l'entrée sont strictement croissantes.
Sortie
Afficher un seul entier — le nombre de triplets de points où la distance entre les deux points les plus éloignés ne dépasse pas d.
Veuillez ne pas utiliser le spécificateur %lld pour lire ou écrire des nombres 64 bits en C++. Il est recommandé d'utiliser cin, cout streams ou le spécificateur %I64d.
| Entrée |
Sortie |
4 3
1 2 3 4
4 |
4 2
-3 -2 -1 0
2 |
5 19
1 10 20 30 50
1 |
;
Dans le premier exemple, trois points différents nous conviennent.
Dans le deuxième exemple, seuls 2 triplets nous conviennent : {-3, -2, -1} et {-2, -1, 0}.
Dans le troisième exemple, un triple nous convient : {1, 10, 20}.