Problem
A pequena Petya adora bolinhas. Recentemente, sua mãe deu a ele n pontos que estão na linha OX. Petya se perguntou de quantas maneiras ele pode escolher três pontos diferentes para que a distância entre os dois pontos mais distantes selecionados não exceda d.
Observe que a ordem dos pontos dentro do trio selecionado não importa.
Entrada
A primeira linha contém dois inteiros: n e d (1 ≤ n ≤ 105; 1 ≤ d ≤ 10< sup>9). A próxima linha contém n inteiros x1, x2, ..., xn, módulo não superior a 109 — coordenadas x de pontos dados a Petya.
É garantido que as coordenadas dos pontos na entrada são estritamente crescentes.
Saída
Imprime um único inteiro — o número de triplos de pontos onde a distância entre os dois pontos mais distantes não excede d.
Por favor, não use o especificador %lld para ler ou escrever números de 64 bits em C++. Recomenda-se usar fluxos cin, cout ou o especificador %I64d.
| Entrada |
Saída |
|
4 3
1 2 3 4
|
4 |
|
4 2
-3 -2 -1 0
|
2 |
|
5 19
1 10 20 30 50
|
1 |
No primeiro exemplo, quaisquer três pontos diferentes são adequados para nós.
No segundo exemplo, apenas 2 triplos são adequados para nós: {-3, -2, -1} e {-2, -1, 0}.
No terceiro exemplo, um triplo nos serve: {1, 10, 20}.