1910: 恶魔
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：28
解决：8
题目描述
有n个恶魔排列成一条直线，从左到右依次编号为1到n。每个恶魔i具有一个初始血量值ai。
恶魔们有一种特殊的能力：如果恶魔i的血量大于等于他相邻的恶魔（即编号为i-1或i+1的恶魔）的血量，那么他可以杀掉这个相邻的恶魔，但自己的血量会变为被杀恶魔的血量值。每个恶魔在任何时候都只能与其直接相邻的恶魔战斗。
现在，每个恶魔都想要尽可能多地杀掉其他恶魔。给定每个恶魔的初始血量值，你需要计算出在最优策略下，每个恶魔最多可以杀掉多少个同伴。
输入
第一行包含一个整数n(1≤n≤2*105)
第二行包含n个整数a[1],a[2]....,a[n](0≤a[i]≤109)
输出
一行，用空格隔开的 n 个整数。第 i 个整数表示第 i 个恶魔最多可以杀掉多少个同伴。
样例输入 复制
4
1 4 2 4样例输出 复制
0 2 1 2提示
第一个恶魔：无法杀死任何恶魔，所以杀0个；
第二个恶魔：先杀第三个恶魔后，变为2血量，再杀掉第一个恶魔，所以杀2个；
第三个恶魔：当第二个恶魔先杀掉第一个恶魔，血量变为1，第三个恶魔再杀掉第二的恶魔，所以杀1个；
第四个恶魔：第四个恶魔先杀掉第三的恶魔，血量变2，然后让第二个恶魔杀掉第一个恶魔，血量变为1，然后第四个恶魔再杀掉第二恶魔，所以总共杀了2个。