[eJOI2018] 山
题目描述
Innopolis 城里有 $n$ 座山，第 $i$ 座的高度为 $a_i$。
美观起见，当一座山比它两边的山（如果存在）**严格** 地高时，才能在这座山上建房子。
有一台挖掘机，每小时可以将任意一座山的高度降低 $1$，同一时间挖掘机只能在一座山上工作。山的高度可以被降为 $0$ 或负数。
请求出当 $1\leq k\leq \lceil\frac{n}{2}\rceil$ 时，建造 $k$ 座房子（即至少使得 $k$ 座山满足上面的要求）时，挖掘机至少需要工作几小时。
输入输出格式
输入格式
第一行，一个整数 $n$。
第二行，$n$ 个整数 $a_{1\cdots n}$，表示数列 $\{a_i\}$。
输出格式
一行，$\lceil\frac{n}{2}\rceil$ 个整数，第 $i$ 个整数表示 $k=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说明
【样例一解释】
将山 $2$ 的高度降低 $1$，山的高度变为 $1,0,1,1,1$，此时山 $1$ 满足条件。
再将山 $4$ 的高度降低 $1$，山的高度变为 $1,0,1,0,1$，此时山 $1,3,5$ 满足条件。
---
【数据范围】
对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^3$，$1\leq a_i\leq 10^5$。
| 子任务编号 | 分数 | 限制 |
| :----------: | :----------: | :----------: |
| $1$ | $0$ | 样例 |
| $2$ | $7$ | $n=3,a_i\leq 100$ |
| $3$ | $15$ | $n\leq 10,a_i\leq 100$ |
| $4$ | $13$ | $n\leq 100,a_i\leq 100$ |
| $5$ | $18$ | $n\leq 100,a_i\leq 2\times 10^3$ |
| $6$ | $22$ | $n\leq 500$ |
| $7$ | $25$ | 无特殊限制 |
---
来源：[eJOI2018](http://ejoi2018.org/) Problem A「Hills」
说明：翻译来自 [LOJ](https://loj.ac/problem/2813)