#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
mt19937 rng;
uniform_int_distribution <ull> dist(0,1ull<<63);
//#define mp make_pair
inline void print(__int128 x){//输出模板 
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
inline int read()
{
    int X = 0;
    bool flag = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            flag = 0;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        X = (X << 1) + (X << 3) + ch - '0';
        ch = getchar();
    }
    if (flag)
        return X;
    return ~(X - 1);
}
const ll mod = 1e9 + 7,INF = 0x3f3f3f3f;
ll qpow(ll a, ll b)
{
    ll res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
inline int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
inline int lcm(int a, int b) { return a / gcd(a, b) * b; }
const int N = 10010,M = 1000010;

int a[N],f[N][N];
int stmax[N][22], stmin[N][22], mn[N];
int n,tt;
struct node
{
    int id,l;
}stk[N];

void init(){
    mn[0] = -1;
    for (int i = 1; i <= n; i++){
        mn[i] = ((i & (i - 1)) == 0) ? mn[i - 1] + 1 : mn[i - 1];
        stmax[i][0] = stmin[i][0] = a[i];
    }
    for (int j = 1; j <= mn[n]; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++){
            stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << (j - 1))][j - 1]);
            stmin[i][j] = min(stmin[i][j - 1], stmin[i + (1 << (j - 1))][j - 1]);
        }
}

inline int rmq_max(int L, int R){
    int k = mn[R - L + 1];
    return max(stmax[L][k], stmax[R - (1 << k) + 1][k]);
}

inline int rmq_min(int L, int R){
    int k = mn[R - L + 1];
    return min(stmin[L][k], stmin[R - (1 << k) + 1][k]);
}

int cal(int k,int r,int now)
{
    return f[stk[now].id][k]+rmq_max(stk[now].l+1,r)-rmq_min(stk[now].l+1,r);
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    init();
    for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[i][j] = -1;
    f[0][0] = 0;
    for(int k=1;k<=n;k++)
    {
        tt = -1;
        for(int i=1;i<=n;i++)
        {
            if(f[i-1][k-1]!=-1)
            {
                while(tt!=-1&&cal(k-1,i,tt)<=f[i-1][k-1]) tt--;
                stk[++tt] =  {i-1,i-1};    
            }
            if(tt!=-1) f[i][k] = max(cal(k-1,i,0),f[i][k]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<f[n][i]<<'\n';
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin>>t;
    while (t--)
        solve();
    return 0;
}