Felicidades en el grupo
Tim Idín no soporta cumplir años. No solo porque pone de manifiesto el paso del tiempo que nos acerca a todos hacia un final, sino porque los grupos de mensajería instantánea a los que pertenece se llenan de felicitaciones hacia él, convirtiéndole en el centro de atención durante todo el día. Cada mensaje que le mandan le parece que supone una molestia para el resto de integrantes del grupo, que sufren continuas notificaciones en el móvil por mensajes que no son para ellos.
Lo peor es que tampoco puede ignorarlos. Si no agradece las muestras de cariño, da sensación al resto de indiferencia. ¡Algunos podrían incluso pensar que tiene silenciado las notificaciones del grupo! Pero dar las gracias por las felicitaciones no hace sino empeorar la situación: también él contribuye a molestar a todos, duplicando el número de notificaciones que reciben.
Para minimizar las molestias causadas por sus mensajes y, al mismo tiempo, no quedar como un desagradecido, intenta retrasar lo más posible sus respuestas, para que un mismo mensaje sirva para agradecer más de una felicitación. Eso sí, nunca espera más allá de un tiempo máximo, pues considera que es de mala educación tardar mucho en contestar.
Entrada
Cada caso de prueba comienza con un número 1 ≤ n ≤ 100.000 indicando el tiempo máximo que Tim está dispuesto a esperar antes de agradecer una felicitación. A continuación aparecen, ordenados de menor a mayor, los instantes de tiempo en los que los miembros del grupo le han felicitado. Ningún número es mayor que 109.
La lista termina con un 0.
Salida
Por cada caso de prueba el programa escribirá el mínimo número de mensajes de agradecimiento que tiene que escribir Tim para que todos aquellos que le feliciten reciban su respuesta antes de que pase n, el tiempo máximo admitido por Tim.
Si Tim envía un mensaje de agradecimiento en el mismo instante en el que recibe una felicitación, considera que la persona que le ha felicitado se da por respondida.
Entrada de ejemplo
1 1 2 3 4 0 4 2 2 3 7 11 20 0
Salida de ejemplo
2 3