Minimum Excavation Hours for Building Houses on Peaks

In Innopolis city there are n mountains. The i^th mountain has height \(a_i\). For aesthetic reasons, a house can be built on a mountain only if it is strictly higher than its adjacent mountain(s) (if they exist). In other words, for a mountain at position \(i\) its height must satisfy:

• If both neighbors exist (i.e. \(2 \le i \le n-1\)): \(a_i > a_{i-1}\) and \(a_i > a_{i+1}\).
• If it is the first mountain (i.e. \(i=1\)): \(a_1 > a_2\).
• If it is the last mountain (i.e. \(i=n\)): \(a_n > a_{n-1}\).

There is an excavator which in one hour can lower the height of any one mountain by \(1\) (you can lower a mountain as many times as needed – even to \(0\) or negative values). When lowering the heights appropriately, some mountains may become peaks where a house can be built.

Your task is: for every \(k\) from \(1\) to \(\lceil \frac{n}{2} \rceil\), determine the minimum number of hours the excavator must work so that it is possible to build houses on at least \(k\) mountains (i.e. to have at least \(k\) peaks in the array after lowering some mountains appropriately).

Note: Two peaks cannot be adjacent because if two consecutive mountains were peaks then the peak condition of the right one (or left one) would force contradictory inequalities.

The adjustments for different peaks may interact (for example, two peaks that are separated by only one mountain share that valley and may be able to share some lowering work). Compute the minimum total number of hours required.

inputFormat

The first line of input contains a single integer \(n\) (the number of mountains).

The second line contains \(n\) space‐separated integers \(a_1, a_2, \dots, a_n\) representing the heights of the mountains.

outputFormat

Output \(\lceil \frac{n}{2} \rceil\) integers. The \(k\)-th integer (for \(1 \le k \le \lceil \frac{n}{2} \rceil\)) should be the minimum number of hours the excavator must work so that it is possible to have at least \(k\) peaks.

sample

1
5

0