← 返回题目列表

Codeforces · 1012/C

C. 山

中文机器翻译题面 查看原题

欢迎来到Innopolis市。整年里,Innopolis 的居民都承受着无休无止的城市建设的痛苦。

从你房间的窗户,你可以看到 n 个山​​丘的序列,其中第 i 个山丘的高度为 ai。伊诺波利斯政府希望在山上建造一些房屋。然而,为了城市外观,房子只能建在山上,并且严格高于邻近的山(如果有的话)。例如,如果高度顺序为 5、4、6、2,则只能在高度为 5 和 6 的山上建造房屋。

Innopolis政府有一台挖掘机,可以在一小时内将任意山丘的高度降低一个。挖掘机一次只能在一座山上作业。允许将山丘降低到零高度,甚至降低到负值。任何山丘的高度增加都是不可能的。市政府想要建造k栋房屋,因此必须至少有k座山满足上述条件。调整山丘以实现政府计划所需的最短时间是多少?

但是,k 的确切值尚未确定,所以您能否计算 $$1 \leq k \leq \left\lceil \frac{n}{2} \right\rceil$$ 范围内所有 k 的答案?这里 $$\left\lceil \frac{n}{2} \right\rceil$$ 表示 n 除以 2,向上舍入。

输入

输入的第一行包含唯一的整数 n (1 ≤ n ≤ 5000)——序列中山的数量。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 100 000)——序列中山丘的高度。

输出

精确打印 $$\left\lceil \frac{n}{2} \right\rceil$$ 数字,以空格分隔。第 i 个打印数字应等于平整山丘所需的最少小时数,以便可以建造 i 栋房屋。

示例

输入 #1

5
1 1 1 1 1

输出 #1

1 2 2

输入 #2

3
1 2 3

输出 #2

0 2

输入 #3

5
1 2 3 2 2

输出 #3

0 1 3

注意

在第一个示例中,为了获得至少一个适合建造的山丘,可以在一小时内将第二个山丘降低一个,然后高度顺序变为1,0,1,1,1,第一个山丘变得适合建造。

在第一个例子中,要获得至少两个或至少三个合适的山丘,可以降低第二个和第四个山丘,则高度顺序变为1,0,1,0,1,山丘1,3,5变得适合建造。