Problem
Il piccolo Petya ama i puntini. Recentemente, sua madre gli ha dato n punti che si trovano sulla linea OX. Petya si è chiesto in quanti modi può scegliere tre punti diversi in modo che la distanza tra i due più lontani dei punti selezionati non superi d.
Tieni presente che l'ordine dei punti all'interno del trio selezionato non ha importanza.
Input
La prima riga contiene due numeri interi: n e d (1 ≤ n ≤ 105; 1 ≤ d ≤ 10< sup>9). La riga successiva contiene n interi x1, x2, ..., xn, modulo non superiore a 109 — coordinate x dei punti dati a Petya.
È garantito che le coordinate dei punti nell'input siano strettamente crescenti.
Uscita
Stampa un singolo numero intero — il numero di triple di punti in cui la distanza tra i due punti più lontani non supera d.
Non utilizzare l'identificatore %lld per leggere o scrivere numeri a 64 bit in C++. Si consiglia di utilizzare flussi cin, cout o l'identificatore %I64d.
| Input |
Uscita |
|
4 3
1 2 3 4
|
4 |
|
4 2
-3 -2 -1 0
|
2 |
|
5 19
1 10 20 30 50
|
1 |
Nel primo esempio, tre punti diversi sono adatti a noi.
Nel secondo esempio, solo 2 triple sono adatte a noi: {-3, -2, -1} e {-2, -1, 0}.
Nel terzo esempio, una tripla ci sta bene: {1, 10, 20}.