A primera hora de la mañana, el granjero John se despertó con el sonido de la madera astillada. Eran las vacas, ¡y estaban escapando del establo de nuevo!. El granjero John estaba harto de las escapadas matutinas de las vacas y decidió que ya era suficiente: era hora de ponerse duro. Clavó en la pared del establo un contador que registraba el número de días transcurridos desde la última fuga. Así que si una fuga se produjo en la mañana, el contador sería ~0~ ese día; si la última fuga fue hace ~3~ días, el contador marcaría ~3~. El granjero John registraba meticulosamente el contador cada día.

Ha llegado el final del año y el granjero John está dispuesto a hacer cuentas. ¡Las vacas pagarán, dice!. Pero hay algo en su registro que no parece del todo correcto... El granjero John quiere averiguar cuántos escapes se han producido desde que empezó su registro. Sin embargo, sospecha que las vacas han manipulado su registro, y lo único que sabe con seguridad es que lo empezó el día de una fuga. Por favor, ayúdale a determinar, para cada número de fugas que puedan haber ocurrido desde que empezó el registro, el número mínimo de entradas que deben haber sido manipuladas.

Entrada

La primera línea contiene un único número entero ~N(1 \leq N \leq 100)~, que denota el número de días desde que el granjero Juan empezó a registrar el contador de escapes de vacas. La segunda línea contiene ~N~ enteros separados por espacios. El ~i~-esimo entero es un entero no negativo ~a_i~ (como máximo ~100~), indicando que en el día ~i~ el contador estaba en ~a_i~ a menos que las vacas hayan manipulado la entrada del registro de ese día.

Salida

La salida debe consistir en ~N~ enteros, uno por línea. El ~i~-esimo entero debe ser el mínimo sobre todas las posibles secuencias de fuga con ~i~ fugas, del número de entradas de registro que son inconsistentes con esa secuencia.

Ejemplo de Entrada

6 
1 1 2 0 0 1

Ejemplo de Salida

4
2
1
2
3
4

Si sólo hubiera una fuga, el registro correcto sería ~0, 1, 2, 3, 4, 5~, es decir, ~4~ entradas diferentes del registro dado.

Si hubieran dos fugas, el registro correcto sería ~0, 1, 2, 3, 0, 1~, es decir, ~2~ entradas diferentes del registro dado. En este caso, las fugas se produjeron el primer y el quinto día.

Si se produjeron ~3~ fugas, entonces el registro correcto podría ser ~0,1,2,0,0,1~, que es sólo una entrada diferente del registro dado. En este caso, las fugas se produjeron el primer, cuarto y quinto día.

Y así sucesivamente.