Problema número 282

Agujeros en la manguera

Tiempo máximo: 1,000-3,000 sMemoria máxima: 4096 KiB
Manguera

Este verano Susana tiene en el jardín una plaga de hormigas que la tienen tomada con la manguera para regar. Tanto es así que han conseguido ya hacer unos cuantos agujeros para obtener agua y refrescarse.

Después de encargarse de las hormigas, Susana ha decidido arreglar la manguera tapando los agujeros. Para ello tiene que comprar unos parches rectangulares que se colocan a lo largo sobre la manguera y cuyo ancho la envuelve completamente. Un parche puede tapar varios agujeros (si un parche tiene una longitud L puede llegar a tapar agujeros que estén separados entre sí hasta esa distancia) y pueden solaparse.

Susana cuando va a la tienda de jardinería prefiere comprar flores, así que quiere gastarse lo mínimo posible comprando parches. ¿Puedes calcular cuántos parches como mínimo necesita Susana para cubrir todos los agujeros de la manguera?

Entrada

La entrada consta de una serie de casos de prueba. Cada caso comienza con una línea con el número N de agujeros en la manguera (1 ≤ N ≤ 100.000) y la longitud L de los parches (1 ≤ L ≤ 1.000). A continuación aparece una línea con N enteros que representan las posiciones donde se encuentran los agujeros (números enteros entre 1 y 109), medidos desde el comienzo de la manguera (punto 0) y dados en orden creciente desde ese comienzo.

Salida

Para cada caso de prueba se escribirá una línea con el mínimo número de parches necesarios para cubrir todos los agujeros.

Entrada de ejemplo

3 2
1 6 10
3 5
1 6 10
8 10
3 8 8 9 20 45 55 90

Salida de ejemplo

3
2
4