#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<pair<short,short>>loc[maxn];
int n;
int mx[maxn][15],mn[maxn][15];
int now[maxn];
inline int solv(int l,int r){
	int b=log(r-l+1);
	return -min(mn[l][b],mn[r-(1<<b)+1][b])+max(mx[l][b],mx[r-(1<<b)+1][b]);
}
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(solv(x+1,mid)+nx>solv(y+1,mid)+ny)l=mid+1;
		else r=mid;
	}
	return l;
}
void solve(){
	// cin>>n;
	n=1e4;
	for(int i=1;i<=n;i++){
		// cin>>a[i];
		a[i]=i;
		dp[i].resize(i+1);
	}
	dp[0]={0};
	for(int i=n;i>=1;i--){
		mn[i][0]=mx[i][0]=a[i];
		for(int j=1;j<15;j++){
			mn[i][j]=min(mn[i][j-1],mn[min(i+(1<<j-1),n)][j-1]);
			mx[i][j]=max(mx[i][j-1],mx[min(i+(1<<j-1),n)][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		dp[i][1]=solv(1,i);
		dp[i][i]=0;
		loc[i]={{i,0}};
		for(int j=2;j<i;j++){
			while(now[j-1]+1<loc[j-1].size()&&loc[j-1][now[j-1]+1].second<=i)now[j-1]++;
			dp[i][j]=dp[loc[j-1][now[j-1]].first][j-1]+solv(loc[j-1][now[j-1]].first+1,i);
			// cout<<loc[j-1][now[j-1]].first<<" "<<loc[j-1][now[j-1]].second<<" "<<loc[j-1][now[j-1]+1].second<<" "<<loc[j-1].size()<<"\n";
		}
		// cout<<"\n";
		if(i<n)
		for(int j=1;j<i;j++){
			while(loc[j].size()){
				int tmp=loc[j].back().first,nw=find(tmp,i,dp[tmp][j],dp[i][j]);
				// if(0){
				if(nw<=loc[j].back().second){
					loc[j].pop_back();
				}
				else{
					loc[j].push_back({i,nw});
					break;
				}
			}
		}
		// for(int j=1;j<=i;j++)cout<<dp[i][j]<<" ";cout<<"\n";
	}
	for(int j=1;j<=n;j++)cout<<dp[n][j]<<" ";cout<<"\n";
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}
/*
*/