#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define i64 long long
#define endl '\n'
#define lb(x) ((x) & (-x))
using namespace std;
const i64 mod = 1e18+7;
const int maxn = 1e4+10;
i64 dp[2][maxn][4];
signed main()
{
    IOS;
    int n; cin >> n;
    int x = 0;
    memset(dp,-0x3f,sizeof dp);
    dp[0][0][3] = 0;
    for(int i = 1; i <= n; ++i)
    {
        x ^= 1;
        memset(dp[x],-0x3f,sizeof dp[x]);
        int z; cin >> z;
        for(int j = 1; j <= n; ++j)
        {
            dp[x][j][0] = max(dp[x^1][j][0],dp[x^1][j-1][3]);
            dp[x][j][1] = max({dp[x^1][j][1],dp[x^1][j][0] + z,dp[x^1][j-1][3] + z});
            dp[x][j][2] = max({dp[x^1][j][2],dp[x^1][j-1][3] - z,dp[x^1][j][0] - z});
            dp[x][j][3] = max({dp[x^1][j][3],dp[x^1][j-1][3],dp[x^1][j][1] - z,dp[x^1][j][2] + z});
        }
    }
    for(int i = 1; i <= n; ++i) cout << dp[x][i][3] << endl;
    return 0;
}