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

欢迎来到因诺波利斯市。全年之中，因诺波利斯市民都饱受城市持续建设之苦。

从你房间的窗户向外望去，你能看到一列由 $n$ 座山丘组成的序列，其中第 $i$ 座山丘的高度为 $a_i$。因诺波利斯市政府希望在这些山丘上建造若干房屋。然而，为了保持城市美观，一座房屋只能建在严格高于其相邻山丘（如果存在）的山丘上。例如，若高度序列为 $5,\,4,\,6,\,2$，则仅能在高度为 $5$ 和 $6$ 的山丘上建造房屋。

因诺波利斯市政府拥有一台挖掘机，该机器每小时可将任意一座山丘的高度降低 $1$。挖掘机每次只能作用于一座山丘。允许将山丘高度降至 $0$，甚至降为负值；但不允许升高任何山丘的高度。市政府希望建造 $k$ 座房屋，即要求至少有 $k$ 座山丘满足上述条件。那么，为达成该目标，调整山丘所需的最短时间是多少？

然而，确切的 $k$ 值尚未确定，因此请你计算所有 $k$ 在范围 $\left[1, \left\lceil \frac{n}{2} \right\rceil \right]$ 内对应的答案。此处 $\left\lceil \frac{n}{2} \right\rceil$ 表示 $n$ 除以 $2$ 后向上取整。

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 ≤ 100 000)—the heights of the hills in the sequence.

输入的第一行包含唯一一个整数 $n$（$1 ≤ n ≤ 5000$）——序列中山丘的数量。

第二行包含 $n$ 个整数 $a_i$（$1 ≤ a_i ≤ 100\,000$）——序列中山丘的高度。

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.

精确输出 个数字，数字之间用空格分隔。第 i 个输出的数字应等于将山丘整平以使其能够建造 i 座房屋所需的最少小时数。

In the first example, to get at least one hill suitable for construction, one can decrease the second hill by one in one hour, then the sequence of heights becomes 1, 0, 1, 1, 1 and the first hill becomes suitable for construction.

In the first example, to get at least two or at least three suitable hills, one can decrease the second and the fourth hills, then the sequence of heights becomes 1, 0, 1, 0, 1, and hills 1, 3, 5 become suitable for construction.

在第一个例子中，为了至少获得一座适合建造的山丘，可以在一小时内将第二座山丘的高度减少 1，此时高度序列为 $1,\,0,\,1,\,1,\,1$，第一座山丘便成为适合建造的山丘。

在第一个例子中，为了至少获得两座或至少三座适合建造的山丘，可以降低第二座和第四座山丘的高度，此时高度序列为 $1,\,0,\,1,\,0,\,1$，第 1、3、5 座山丘便成为适合建造的山丘。