A11906 | Hills

Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city construction.

From the window in your room, you see the sequence of $n$ hills, where $i$ -th of them has height $a_{i}$ . The Innopolis administration wants to build some houses on the hills. However, for the sake of city appearance, a house can be only built on the hill, which is strictly higher than neighbouring hills (if they are present). For example, if the sequence of heights is $5,4,6,2$ , then houses could be built on hills with heights $5$ and $6$ only.

The Innopolis administration has an excavator, that can decrease the height of an arbitrary hill by one in one hour. The excavator can only work on one hill at a time. It is allowed to decrease hills up to zero height, or even to negative values. Increasing height of any hill is impossible. The city administration wants to build $k$ houses, so there must be at least $k$ hills that satisfy the condition above. What is the minimum time required to adjust the hills to achieve the administration's plan?

However, the exact value of $k$ is not yet determined, so could you please calculate answers for all $k$ in range ? Here  denotes $n$ divided by two, rounded up.

The first line of input contains the only integer $n$ ( $1<=n<=5000$ )—the number of the hills in the sequence.

Second line contains $n$ integers $a_{i}$ ( $1<=a_{i}<=100000$ )—the heights of the hills in the sequence.

Print exactly  numbers separated by spaces. The $i$ -th printed number should be equal to the minimum number of hours required to level hills so it becomes possible to build $i$ houses.