题目描述

Innopolis 城里有 $n$ 座山，第 $i$ 座的高度为 $a_i$。
美观起见，当一座山比它两边的山（如果存在）严格地高 时，才能在这座山上建房子。

有一台挖掘机，每小时可以将任意一座山的高度降低 $1$，同一时间挖掘机只能在一座山上工作。山的高度可以被降为 $0$ 或负数。

请求出当 $1 \le k \le \lceil \frac{n}{2} \rceil$ 时，建造 $k$ 座房子（即至少使得 $k$ 座山满足上面的要求）时，挖掘机至少需要工作几小时。

---

输入格式

第一行，一个整数 $n$ $(1 \le n \le 5000)$。
第二行，$n$ 个整数 $a_1, a_2, a_3, \dots, a_n$，表示数列 $\{a_i\}$，其中 $1 \le a_i \le 10^5$。

---

输出格式

一行，$\lceil \frac{n}{2} \rceil$ 个整数，第 $i$ 个整数表示 $k=i$ 时的答案。

---

样例 1

输入

5
1 1 1 1 1

输出

1 2 2

解释：
将山 $2$ 的高度降低 $1$，山的高度变为 $1, 0, 1, 1, 1$，此时山 $1$ 满足条件。
再将山 $4$ 的高度降低 $1$，山的高度变为 $1, 0, 1, 0, 1$，此时山 $1, 3, 5$ 满足条件。

---

样例 2

输入

3
1 2 3

输出

0 2

---

样例 3

输入

5
1 2 3 2 2

输出

0 1 3

---

数据范围与提示

子任务编号	分数	限制
1	$0$	样例
2	$7$	$n = 3$, $a_i \le 100$
3	$15$	$n \le 10$, $a_i \le 100$
4	$13$	$n \le 100$, $a_i \le 100$
5	$18$	$n \le 100$, $a_i \le 2000$
6	$22$	$n \le 500$
7	$25$	无特殊限制