RT

#include<bits/stdc++.h>//二维状态表示到了第i座山，建了j个房子，当前山必须建的最小花费
using namespace std;
int n,min1[5001],r[5001],l[5001],dp[5001][5001],a[5001],max1[5001];
int qs(int x){
	if(x%2==0){
		return x/2;
	}
	else{
		return x/2+1;
	}
}
int main(){
	std::ios::sync_with_stdio(false);
	freopen("hills.in","r",stdin);
	freopen("hills.out","w",stdout);
	cin>>n;
	memset(min1,10,sizeof(min1));
	memset(max1,10,sizeof(max1));
	memset(dp,10,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		if(a[i+1]>=a[i]){
			r[i]=a[i+1]-a[i]+1;
		}
	}
	for(int i=2;i<=n;i++){
		if(a[i-1]>=a[i]){
			l[i]=a[i-1]-a[i]+1;
		}
	}
	dp[1][1]=r[1];
	dp[2][1]=r[2]+l[2];
	max1[1]=min(r[1],r[2]+l[2]);
	min1[1]=min(dp[1][1],dp[2][1]);
	for(int i=3;i<=n;i++){
		for(int j=1;j<=qs(i);j++){
			if(j==1){
				dp[i][j]=l[i]+r[i];
				min1[j]=min(min1[j],dp[i][j]);
				continue;
			}
			max1[j-1]=min(max1[j-1],dp[i-2][j-1]);
			if(max1[j-1]==dp[i-2][j]){
				if(r[i-2]>=l[i]){
					dp[i][j]=dp[i-2][j-1]+r[i];
					
				}
				else{
					dp[i][j]=dp[i-2][j-1]-r[i-2]+l[i]+r[i];
				}
			}
			else{
				
				dp[i][j]=max1[j-1]+l[i]+r[i];
			}
			min1[j]=min(min1[j],dp[i][j]);
		}
	}
	for(int i=1;i<=qs(n);i++){
		cout<<min1[i]<<' ';
	}
}