Breakout Accounting

Farmer John has been keeping a daily log recording the number of days since the last cow breakout from the barn. On any day:

• If a breakout occurs in the morning then the counter is set to \(0\).
• If no breakout occurs then the counter should be equal to the number of days elapsed since the most recent breakout.

Farmer John started his log on a day when a breakout occurred, so the log begins with a counter reading that should be \(0\). However, he suspects that his log may have been tampered with. Given the recorded log over \(n\) days, your task is to determine, for each possible total number of breakouts (from \(1\) to \(n\)) that might have occurred, the minimum number of log entries that must have been altered to make the log internally consistent.

More formally, let \(a_1,a_2,\dots,a_n\) be the logged counter readings. If a breakout occurs on a day then the expected counter reading for that day is \(0\), and on any day that does not have a breakout, the expected counter reading is the number of days since the most recent breakout. You must assume that a breakout definitely occurred on day \(1\). For each possible number \(b\) of breakouts (with \(1\le b\le n\)), compute the minimum number of entries that must be changed so that there is some selection of \(b\) days (with day \(1\) fixed as a breakout) for which the log matches the rule: for every day \(i\), if the most recent breakout happened on day \(j\le i\) then the correct counter reading should be \(i-j\) (with the special case \(i=j\) giving \(0\)).

inputFormat

The first line of input contains a single integer \(n\) (the number of days). The next \(n\) lines each contain an integer, representing the logged counter reading for that day.

outputFormat

Output \(n\) lines. On the \(b^{th}\) line (\(1\le b\le n\)), output the minimum number of entries that need to be changed so that the log is consistent with exactly \(b\) breakouts having occurred.

sample

4
1
1
2
0

2
1
3
3