Domando al Rebaño (Oro)#10413
Temprano en la mañana, el Granjero John se despertó por el estruendo de un árbol al romperse. ¡Eran las vacas, que de nuevo se escapaban del establo!
El Granjero John estaba harto hasta la médula de las fugas matutinas de las vacas, y decidió que ya era suficiente: había llegado el momento de tomar medidas drásticas. Clavó en la pared del establo un contador que muestra la cantidad de días transcurridos desde la última fuga. Así, si la fuga ocurrió por la mañana, ese mismo día el contador muestra ; si la última fuga fue hace días, el contador muestra . El Granjero John anotaba escrupulosamente cada día las lecturas del contador en un registro.
Ha llegado el final del año, y el Granjero John está listo para hacer un balance. ¡Las vacas pagarán por todo, dice él! Pero algo en su registro no parece estar del todo correcto...
El Granjero John quiere averiguar cuántas fugas ocurrieron desde el momento en que comenzó a llevar el registro. Sin embargo, sospecha que las vacas falsificaron algunas anotaciones del registro, y lo único que sabe con certeza es que comenzó a llevar el registro justo el día de una fuga. Ayúdale a determinar, para cada posible cantidad de fugas desde el inicio del registro, la cantidad mínima de anotaciones que debieron haber sido falsificadas.
La primera línea contiene un único entero n~(1 \le n \le 100) — la cantidad de días desde que el Granjero John comenzó a anotar las lecturas del contador de fugas.
La segunda línea contiene enteros a_1, a_2, \ldots, a_n~(0 \le a_i \le 100), donde a_i es la lectura del contador en el día , a menos que las vacas hayan falsificado la anotación de ese día.
Imprime enteros, uno por línea. El -ésimo número debe ser igual a la cantidad mínima de anotaciones del registro que no concuerdan con una secuencia de fugas que contenga exactamente fugas. El mínimo se toma sobre todas esas secuencias posibles.
Ejemplo 1
Si hubo solo fuga, el registro correcto sería 0, 1, 2, 3, 4, 5, que difiere del registro dado en anotaciones.
Si hubo fugas, el registro correcto podría ser 0, 1, 2, 3, 0, 1, que difiere del registro dado en anotaciones. En este caso, las fugas ocurrieron el primer y el quinto día.
Si hubo fugas, el registro correcto podría ser 0, 1, 2, 0, 0, 1, que difiere del registro dado en solo anotación. En este caso, las fugas ocurrieron el primer, el cuarto y el quinto día.
Y así sucesivamente.