Ir al contenido (saltar navegación)

Villancicos al viento

Tiempo máximo: 1,000-4,000 sMemoria máxima: 16384 KiB
Fila de casas unifamiliares

En Villa Cinco son muy aficionados a los villancicos. María Morena vive en una de sus calles, de casitas bajas unifamiliares, donde la mayoría de los vecinos ponen sus villancicos favoritos en las fechas señaladas.

Esta nochevieja sopla un fuerte viento del este, por lo que la música puesta en una casa es arrastrada por el aire y se escucha en varias de las casas calle abajo. Dependiendo del volumen, llegará más o menos lejos.

Dado el número de casas a las que llegan los villancicos puestos en cada vivienda de la calle, ¿cuántas oyen música de algún vecino?

Entrada

La entrada está compuesta por distintos casos de prueba, cada uno ocupando dos líneas.

La primera línea de cada caso contiene el número 1 ≤ n ≤ 500.000 de casas de la calle. La segunda línea contiene la distancia a la que llegan, hacia la izquierda, los villancicos puestos por cada una de las n casas. Por ejemplo, un 1 indica que los villancicos de esa vivienda son oídos por la situada inmediatamente antes. Ninguna casa pone la música tan alta como para que sea escuchada más allá de 500.000 casas.

La entrada termina con un caso de prueba sin viviendas, que no deberá ser procesado.

Salida

Por cada caso de prueba, el programa escribirá cuántas casas de la calle escuchan música de alguno de los vecinos calle arriba.

Entrada de ejemplo

3
1 0 1
5
0 1 0 1 2
0

Salida de ejemplo

1
3