P4267 [USACO18FEB] Taming the Herd G

题目描述

清晨，Farmer John 被木头碎裂的声音吵醒。原来是奶牛们又一次从谷仓里逃出来了！ Farmer John 对奶牛们的清晨逃跑行为感到厌烦，他决定受够了：是时候采取强硬措施了。他在谷仓的墙上钉了一个计数器，用于记录自上次逃跑以来的天数。因此，如果某天早上发生了逃跑，计数器当天会显示 $0$；如果最近一次逃跑发生在 $3$ 天前，计数器会显示 $3$。Farmer John 每天都会仔细记录计数器的值。

年末到了，Farmer John 准备进行一些统计。他说，奶牛们要为此付出代价！但他发现他的记录似乎有些不对劲……

Farmer John 想知道自从他开始记录以来发生了多少次逃跑。然而，他怀疑奶牛们篡改了他的记录，他唯一能确定的是他开始记录的那天发生了一次逃跑。请帮助他确定，对于可能发生的逃跑次数，记录中必须被篡改的最小条目数。

输入格式

第一行包含一个整数 $N$（$1 \leq N \leq 100$），表示 Farmer John 开始记录奶牛逃跑计数器以来的天数。 第二行包含 $N$ 个以空格分隔的整数。第 $i$ 个整数是一个非负整数 $a_i$（最多 $100$），表示第 $i$ 天计数器的值为 $a_i$，除非奶牛篡改了那天的记录。

输出格式

输出应包含 $N$ 个整数，每行一个。第 $i$ 个整数应表示在所有可能的逃跑序列中，发生 $i$ 次逃跑时，与序列不一致的记录条目的最小数量。

输入输出样例 1

6
1 1 2 0 0 1

4
2
1
2
3
4

说明/提示

如果只有 $1$ 次逃跑，那么正确的记录应该是 0 1 2 3 4 5，这与给定的记录有 $4$ 个条目不同。

如果有 $2$ 次逃跑，那么正确的记录可能是 0 1 2 3 0 1，这与给定的记录有 $2$ 个条目不同。在这种情况下，逃跑发生在第 $1$ 天和第 $5$ 天。

如果有 $3$ 次逃跑，那么正确的记录可能是 0 1 2 0 0 1，这与给定的记录只有 $1$ 个条目不同。在这种情况下，逃跑发生在第 $1$ 天、第 $4$ 天和第 $5$ 天。

以此类推。

题目来源：Brian Dean 和 Dhruv Rohatgi