题目描述

本题译自 eJOI2018 Problem A. Hills

Innopolis 城里有 $n$ 座山，第 $i$ 座的高度为 $a_i$。
美观起见，当一座山比它两边的山（如果存在）严格地高时，才能在这座山上建房子。
有一台挖掘机，每小时可以将任意一座山的高度降低 $1$，同一时间挖掘机只能在一座山上工作。山的高度可以被降为 $0$ 或负数。
请求出当 $1 \le k \le \lceil \frac{n}{2} \rceil$ 时，建造 $k$ 座房子（即至少使得 $k$ 座山满足上面的要求）时，挖掘机至少需要工作几小时。

输入格式

第一行，$1$ 个整数 $n\ (1 \le n \le 5000)$。
第二行，$n$ 个整数 $a_1, a_2, a_3, \cdots 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$ 满足条件。

3
1 2 3

0 2

5
1 2 3 2 2

0 1 3

数据范围与提示

数据限制