#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define lowbit(x) (x&-x)
#define log(x) (31^__builtin_clz(x))
using namespace std;
const int maxn=1e4+5;
int a[maxn];
vector<int>dp[maxn];
vector<int>ans[maxn];
vector<short>loc[maxn];
int n;
int now[maxn];
short find(int x,int y,int nx,int ny){
	short l=y+1,r=n+1;
	while(l<r){
		short mid=l+r-1>>1;
		if(ans[x+1][mid-(x+1)]+nx>ans[y+1][mid-(y+1)]+ny)l=mid+1;
		else r=mid;
	}
	return l;
}
void solve(){
	n=5e3;
	cin>>n;
	for(int i=1;i<=n;i++){
		a[i]=i;
		cin>>a[i];
		dp[i].resize(i+1);
	}
	for(int i=1;i<=n;i++){
		int mn=a[i],mx=a[i];
		for(int j=i;j<=n;j++){
			mx=max(mx,a[j]);
			mn=min(mn,a[j]);
			ans[i].push_back(mx-mn);
		}
	}
	dp[0]={0};
	
	for(int i=1;i<=n;i++){
		dp[i][1]=ans[1][i-1];
		dp[i][i]=0;
		loc[i]={(short)i};
		for(int j=2;j<i;j++){
			while(now[j-1]+1<loc[j-1].size()&&find(loc[j-1][now[j-1]],loc[j-1][now[j-1]+1],dp[loc[j-1][now[j-1]]][j-1],dp[loc[j-1][now[j-1]+1]][j-1])<=i)now[j-1]++;
			dp[i][j]=dp[loc[j-1][now[j-1]]][j-1]+ans[loc[j-1][now[j-1]]+1][i-(loc[j-1][now[j-1]]+1)];
			// cout<<loc[j-1][now[j-1]]<<" "<<loc[j-1].size()<<"\n";
		}
		// cout<<"\n";
		if(i<n)
		for(int j=1;j<i;j++){
			while(loc[j].size()>1){
				int tmp=loc[j].back(),tmp1=loc[j][loc[j].size()-2];
				int nw=find(tmp,i,dp[tmp][j],dp[i][j]);
				int lst=find(tmp,tmp1,dp[tmp][j],dp[tmp1][j]);
				// if(0){
				if(nw<=lst){
					loc[j].pop_back();
				}
				else{
					break;
				}
			}
			loc[j].push_back(i);
		}
		// for(int j=1;j<=i;j++)cout<<dp[i][j]<<" ";cout<<"\n\n";
	}
	for(int j=1;j<=n;j++)cout<<dp[n][j]<<"\n";
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}
/*
*/