欢迎来到因诺波利斯（Innopolis）市。全年，因诺波利斯的市民们都饱受永无止境的城市建设之苦。

从你的房间窗户望去，你可以看到一排 $n$ 座山丘，其中第 $i$ 座山丘的高度为 $a_i$。因诺波利斯政府想要在这些山丘上建造一些房屋。然而，为了城市的美观，房屋只能建在严格高于其相邻山丘（如果存在的话）的山丘上。例如，如果高度序列为 $5, 4, 6, 2$，那么房屋只能建在高度为 $5$ 和 $6$ 的山丘上。

因诺波利斯政府有一台挖掘机，可以在一小时内将任意一座山丘的高度降低 $1$。挖掘机一次只能在一座山丘上工作。山丘的高度可以被降低到 $0$，甚至是负数。无法增加任何山丘的高度。市政府想要建造 $k$ 座房屋，因此必须至少有 $k$ 座山丘满足上述条件。为了实现政府的计划，调整山丘所需的最短时间是多少？

然而，$k$ 的确切值尚未确定，所以你能否计算出所有 $1 \le k \le \lceil \frac{n}{2} \rceil$ 的答案？这里 $\lceil \frac{n}{2} \rceil$ 表示 $n$ 除以 $2$ 并向上取整。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5000$)，表示序列中山丘的数量。 第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le 100\,000$)，表示序列中山丘的高度。

输出格式

输出 $\lceil \frac{n}{2} \rceil$ 个用空格分隔的数字。第 $i$ 个输出的数字应等于为了能够建造 $i$ 座房屋而调整山丘所需的最短小时数。

子任务

1. (7 分) $n = 3, a_i \le 100$
2. (15 分) $n \le 10, a_i \le 100$
3. (13 分) $n \le 100, a_i \le 100$
4. (18 分) $n \le 100, a_i \le 2000$
5. (22 分) $n \le 500$
6. (25 分) $n \le 5000$

样例

样例输入 1

5
1 1 1 1 1

样例输出 1

1 2 2

样例输入 2

3
1 2 3

样例输出 2

0 2

样例输入 3

5
1 2 3 2 2

样例输出 3

0 1 3

说明

在第一个样例中，为了获得至少一座适合建造的房屋，可以将第二座山丘降低 $1$ 小时，此时高度序列变为 $1, 0, 1, 1, 1$，第一座山丘变得适合建造。

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