欢迎来到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变得适合建造。