Hills

题意翻译

给你 $n$ 个数，你一次操作可以把某一个数减一（可以减为负数），你的目标是使任意的 $k$ 个数严格大于它旁边的两个数（第一个数只用严格大于第二个数，第 $n$ 个数只用严格大于第 $n-1$ 个数），问最少需要几次操作。 $k$ 是不确定的，请输出 $k∈[1,\left\lceil\dfrac{n}{2}\right\rceil]$ 时的答案。 ### 输入格式 第一行一个正整数 $n$。 第二行 $n$ 个正整数 $a_i$。 ### 输出格式 一行 $\left\lceil\dfrac{n}{2}\right\rceil$ 个数，第 $i$ 个数代表 $k=i$ 时的答案 ### 数据范围 $1≤n≤5000$ $1≤ai≤100000$

题目描述

Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city construction. From the window in your room, you see the sequence of $ n $ hills, where $ i $ -th of them has height $ a_{i} $ . The Innopolis administration wants to build some houses on the hills. However, for the sake of city appearance, a house can be only built on the hill, which is strictly higher than neighbouring hills (if they are present). For example, if the sequence of heights is $ 5,4,6,2 $ , then houses could be built on hills with heights $ 5 $ and $ 6 $ only. The Innopolis administration has an excavator, that can decrease the height of an arbitrary hill by one in one hour. The excavator can only work on one hill at a time. It is allowed to decrease hills up to zero height, or even to negative values. Increasing height of any hill is impossible. The city administration wants to build $ k $ houses, so there must be at least $ k $ hills that satisfy the condition above. What is the minimum time required to adjust the hills to achieve the administration's plan? However, the exact value of $ k $ is not yet determined, so could you please calculate answers for all $ k $ in range ? Here  denotes $ n $ divided by two, rounded up.

输入输出格式

输入格式

The first line of input contains the only integer $ n $ ( $ 1<=n<=5000 $ )—the number of the hills in the sequence. Second line contains $ n $ integers $ a_{i} $ ( $ 1<=a_{i}<=100000 $ )—the heights of the hills in the sequence.

输出格式

Print exactly  numbers separated by spaces. The $ i $ -th printed number should be equal to the minimum number of hours required to level hills so it becomes possible to build $ i $ houses.

输入输出样例

输入样例 #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 

说明

In the first example, to get at least one hill suitable for construction, one can decrease the second hill by one in one hour, then the sequence of heights becomes $ 1,0,1,1,1 $ and the first hill becomes suitable for construction. In the first example, to get at least two or at least three suitable hills, one can decrease the second and the fourth hills, then the sequence of heights becomes $ 1,0,1,0,1 $ , and hills $ 1,3,5 $ become suitable for construction.