Description

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).

Input Format

The first line contains one integer $n$.

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

Output Format

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

5
1 1 1 1 1

1 2 2

3
1 2 3

0 2

5
1 2 3 2 2

0 1 3

Hint

[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$.

Source: eJOI2018 Problem A “Hills”.

Note: The translation is from LOJ.

Translated by ChatGPT 5