山丘建房 - 代码源竞赛平台

题目描述

蜗蜗住在一座不断施工的城市。从窗边看出去，有 $n$ 座从左到右排列的山丘，第 $i$ 座的高度为 $a_i$。城市计划在山丘上建房：只有一座山丘严格高于它存在的每一座相邻山丘时，才能在上面建房。最左和最右的山丘分别只有一个相邻山丘。

施工队有一台挖掘机，每工作一小时，可以选择一座山丘并把高度降低 $1$；同一时间只能处理一座山丘。山丘可以降到 $0$ 或负数，但不能增高。

对于每个 $k=1,2,\ldots,\lceil n/2\rceil$，求使至少 $k$ 座山丘能够建房的最少施工小时数。

输入格式

第一行包含一个整数 $n$，表示山丘数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，依次表示每座山丘的初始高度。

输出格式

输出一行 $\lceil n/2\rceil$ 个整数，以空格分隔。第 $k$ 个数表示使至少 $k$ 座山丘能够建房的最少小时数。

样例

3
1 1 1

1 1

5
5 1 4 1 5

0 0 0

样例解释

样例 1 中，把中间山丘从高度 $1$ 降为 $0$，耗时 $1$ 小时。此时两侧山丘都比相邻山丘高，因此建 $1$ 栋或 $2$ 栋房子的最少时间都是 $1$ 小时。

样例 2 中，第 $1$、第 $3$、第 $5$ 座山丘原本就严格高于各自的相邻山丘，不必施工。

数据范围

对于 100% 的数据，保证 $1\le n\le 5000$，$1\le a_i\le 10^5$。