题目描述

Innopolis 城里有 $n$ 座山，第 $i$ 座的高度为 $a_i$。

美观起见，当一座山比它两边的山（如果存在）严格 地高时，才能在这座山上建房子。

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

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

输入格式

第一行，一个整数 $n$。

第二行，$n$ 个整数 $a_{1\cdots n}$，表示数列 $\{a_i\}$。

输出格式

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

5
1 1 1 1 1

1 2 2

3
1 2 3

0 2

5
1 2 3 2 2

0 1 3

提示

【样例一解释】

将山 $2$ 的高度降低 $1$，山的高度变为 $1,0,1,1,1$，此时山 $1$ 满足条件。

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

【数据范围】

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^3$，$1\leq a_i\leq 10^5$。

来源：eJOI2018 Problem A「Hills」

说明：翻译来自 LOJ