Problem Description

In Innopolis city, there are $n$ hills, with the height of the $i$-th hill being $a_i$.

For aesthetic reasons, a house can only be built on a hill that is strictly higher than its neighboring hills (if they exist).

There is a excavator that can reduce the height of any hill by $1$ per hour. The excavator can only work on one hill at a time. The height of a hill can be reduced to $0$ or even negative.

You are required to find out, for $1 \leq k \leq \lceil \frac{n}{2} \rceil$, the minimum number of hours the excavator needs to work to build $k$ houses (i.e., at least $k$ hills must meet the above requirement).

Input Format

The first line contains an integer $n$.

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

Output Format

One line containing $\lceil \frac{n}{2} \rceil$ integers, where the $i$-th integer represents the answer when $k = i$.

Sample Input and Output

Sample Input #1

5
1 1 1 1 1

Sample Output #1

1 2 2

Sample Input #2

3
1 2 3

Sample Output #2

0 2

Sample Input #3

5
1 2 3 2 2

Sample Output #3

0 1 3

Notes

Explanation of Sample #1

Reduce the height of hill $2$ by $1$, changing the heights to $1, 0, 1, 1, 1$. Now hill $1$ meets the condition.

Then reduce the height of hill $4$ by $1$, changing the heights to $1, 0, 1, 0, 1$. Now hills $1, 3, 5$ meet the condition.

Data Range

For $100\%$ of the data, $1 \leq n \leq 5 \times 10^3$, $1 \leq a_i \leq 10^5$.

Source: eJOI2018 Problem A "Hills"

Note: Translation from LOJ

见题面 Input 部分

见题面 Output 部分