P6304 [eJOI 2018] Mountains

There are $n$ mountains in the city of Innopolis. The height of the $i$-th mountain is $a_i$. For beauty, you can build a house on a mountain only if it is **strictly** higher than the mountains on both sides of it (if they exist). There is an excavator. Each hour, it can decrease the height of any one mountain by $1$. At the same time, the excavator can work on only one mountain. A mountain’s height can be reduced to $0$ or negative. For each $1\leq k\leq \lceil\frac{n}{2}\rceil$, find the minimum number of hours the excavator needs to work in order to build $k$ houses (that is, to make at least $k$ mountains satisfy the condition above).

The first line contains one integer $n$. The second line contains $n$ integers $a_{1\cdots n}$, representing the sequence $\{a_i\}$.

Output one line with $\lceil\frac{n}{2}\rceil$ integers. The $i$-th integer is the answer when $k=i$.

[Explanation for Sample 1] Decrease the height of mountain $2$ by $1$. The heights become $1,0,1,1,1$. Now mountain $1$ satisfies the condition. Then decrease the height of mountain $4$ by $1$. The heights become $1,0,1,0,1$. Now mountains $1,3,5$ satisfy the condition. --- [Constraints] For $100\%$ of the testdata, $1\leq n\leq 5\times 10^3$, $1\leq a_i\leq 10^5$. | Subtask ID | Score | Constraints | | :----------: | :----------: | :----------: | | $1$ | $0$ | Sample | | $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$ | No special constraints | --- Source: [eJOI2018](http://ejoi2018.org/) Problem A “Hills”. Note: The translation is from [LOJ](https://loj.ac/problem/2813). Translated by ChatGPT 5