Problem
A la pequeña Petya le encantan los puntos. Recientemente, su madre le dio n puntos que se encuentran en la línea OX. Petya se preguntó de cuántas maneras puede elegir tres puntos diferentes para que la distancia entre los dos puntos seleccionados más lejanos no exceda d.
Tenga en cuenta que el orden de los puntos dentro del trío seleccionado no importa.
Entrada
La primera línea contiene dos números enteros: n y d (1 ≤ n ≤ 105; 1 ≤ d ≤ 10< sup>9). La siguiente línea contiene n enteros x1, x2, ..., xn, módulo no superior a 109 — coordenadas x de los puntos dados a Petya.
Se garantiza que las coordenadas de los puntos en la entrada son estrictamente crecientes.
Salida
Imprimir un solo entero — el número de triples de puntos donde la distancia entre los dos puntos más lejanos no excede d.
No utilice el especificador %lld para leer o escribir números de 64 bits en C++. Se recomienda utilizar cin, cout streams o el especificador %I64d.
| Entrada |
Salida |
|
4 3
1 2 3 4
|
4 |
|
4 2
-3 -2 -1 0
|
2 |
|
5 19
1 10 20 30 50
|
1 |
En el primer ejemplo, tres puntos diferentes son adecuados para nosotros.
En el segundo ejemplo, solo nos convienen 2 triples: {-3, -2, -1} y {-2, -1, 0}.
En el tercer ejemplo, nos queda un triple: {1, 10, 20}.