8080: Taming the Herd

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:5 通过:4

题目描述

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 enough was enough: it was time to get tough. He nailed to the barn wall a counter tracking the number of days since the last breakout. So if a breakout occurred in the morning, the counter would be 00 that day; if the most recent breakout was 33 days ago, the counter would read 33. Farmer John meticulously logged 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 his log, and all he knows for sure is that he started his log on the day of a breakout. Please help him determine, for each number of breakouts that might have occurred since he started the log, the minimum number of log entries that must have been tampered with.

INPUT FORMAT (file taming.in):

The first line contains a single integer NN (1≤N≤1001≤N≤100), denoting the number of days since Farmer John started logging the cow breakout counter. The second line contains NN space-separated integers. The iith integer is a non-negative integer aiai (at most 100100), indicating that on day ii the counter was at aiai, unless the cows tampered with that day's log entry.

OUTPUT FORMAT (file taming.out):

The output should consist of NN integers, one per line. The iith integer should be the minimum over all possible breakout sequences with ii breakouts, of the number of log entries that are inconsistent with that sequence.

SAMPLE INPUT:

6
1 1 2 0 0 1

SAMPLE OUTPUT:

4
2
1
2
3
4

If there was only 1 breakout, then the correct log would look like 0 1 2 3 4 5, which is 4 entries different from the given log.

If there were 2 breakouts, then the correct log might look like 0 1 2 3 0 1, which is 2 entries different from the given log. In this case, the breakouts occurred on the first and fifth days.

If there were 3 breakouts, then the correct log might look like 0 1 2 0 0 1, which is just 1 entry different from the given log. In this case, the breakouts occurred on the first, fourth, and fifth days.

And so on.

输入样例 复制

6
1 1 2 0 0 1

输出样例 复制

4
2
1
2
3
4