Taming the Herd (Gold)#10413
Early in the morning, Farmer John woke up to the sound of splintering wood. It was the cows, and they were breaking out of the barn again!
Farmer John was sick and tired of the cows' morning breakouts, and he decided that enough was enough: it was time to get tough. He nailed a counter to the barn wall that tracks the number of days since the last breakout. So if a breakout occurred in the morning, the counter shows that day; if the most recent breakout was days ago, the counter shows . Farmer John meticulously recorded the value of the counter every day.
The end of the year has come, and Farmer John is ready to do some accounting. The cows will pay, he says! But something about his log doesn't look quite right...
Farmer John wants to find out how many breakouts have occurred since he started his log. However, he suspects that the cows have tampered with the log, and all he knows for sure is that he started it on the day of a breakout. Help him determine, for each possible number of breakouts since he started the log, the minimum number of log entries that must have been tampered with.
The first line contains a single integer n~(1 \le n \le 100) — the number of days since Farmer John started logging the breakout counter.
The second line contains integers a_1, a_2, \ldots, a_n~(0 \le a_i \le 100), where a_i is the value of the counter on day , unless the cows tampered with that day's log entry.
Print integers, one per line. The -th integer should be the minimum number of log entries that are inconsistent with a breakout sequence containing exactly breakouts, taken over all such sequences.
Example 1
If there was only breakout, the correct log would be 0, 1, 2, 3, 4, 5, which differs from the given log in entries.
If there were breakouts, the correct log might be 0, 1, 2, 3, 0, 1, which differs from the given log in entries. In this case, the breakouts occurred on the first and fifth days.
If there were breakouts, the correct log might be 0, 1, 2, 0, 0, 1, which differs from the given log in just entry. In this case, the breakouts occurred on the first, fourth and fifth days.
And so on.