#include<bits/stdc++.h>
using namespace std;
const int MAX=1e4+5;
long long f[MAX][2][3][2];
int a[MAX],n,k;
long long ans[MAX];
int main(){
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>n;
    k=n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    
    int mins=1e9,maxs=-1e9;
    for(int i=1;i<=n;++i){
        mins=min(mins,a[i]);
        maxs=max(maxs,a[i]);
        f[i][0][0][0]=maxs-mins;
        f[i][0][1][1]=f[i][0][1][0]=maxs;
        f[i][0][2][1]=mins,f[i][0][2][0]=-mins;
    }
    ans[1]=f[n][0][0][0];

    int pre=0;
    for(int j=2;j<=k;++j){
        int cur=(pre^1);
        for(int i=0;i<=n;++i)
            f[i][cur][0][0]=f[i][cur][1][0]=f[i][cur][2][0]=-1e13;

        for(int i=j;i<=n;++i){
            f[i][cur][0][0]=max(f[i-1][pre][0][0],max(f[i-1][cur][1][0]-a[i],f[i-1][cur][2][0]+a[i]));

            if(a[i]>f[i-1][cur][1][1])
                f[i][cur][1][0]=f[i-1][cur][1][0]-f[i-1][cur][1][1]+a[i],f[i][cur][1][1]=a[i];
            else
                f[i][cur][1][0]=f[i-1][cur][1][0],f[i][cur][1][1]=f[i-1][cur][1][1];
            if(f[i-1][pre][0][0]+a[i]>f[i][cur][1][0]){
                f[i][cur][1][1]=a[i];
                f[i][cur][1][0]=f[i-1][pre][0][0]+a[i];
            }

            if(a[i]<f[i-1][cur][2][1])
                f[i][cur][2][0]=f[i-1][cur][2][0]+f[i-1][cur][2][1]-a[i],f[i][cur][2][1]=a[i];
            else
                f[i][cur][2][0]=f[i-1][cur][2][0],f[i][cur][2][1]=f[i-1][cur][2][1];
            if(f[i-1][pre][0][0]-a[i]>f[i][cur][2][0]){
                f[i][cur][2][1]=a[i];
                f[i][cur][2][0]=f[i-1][pre][0][0]-a[i];
            }
        }
        ans[j]=f[n][cur][0][0];
        pre=cur;
    }

    for(int i=1;i<=k;++i){
        cout<<ans[i]<<"\n";
    }
}