// Problem: A. Sliding
// Contest: Codeforces - Codeforces Global Round 27
// URL: https://codeforces.com/contest/2035/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define PII pair<int,int>
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int N = 100010;
const int mod = 1e9 + 7;
const int dom = 1e9 + 9;
const int maxn = 1e6 + 5;
int n,m;
int a[N];
void solve(){
	cin >> n;
	vector <vector <vector<int>>> dp(10,vector <vector<int>>(n + 5,vector <int>(n + 5)));
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
	}
	//0max,1min,2maxn ans min, 3 !min!max
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= i; j ++)
		{
			//合并左边
			dp[0][i][j] = dp[3][i - 1][j] + a[i];
			dp[1][i][j] = dp[3][i - 1][j] - a[i];
			dp[2][i][j] = dp[2][i - 1][j];
			dp[2][i][j] = max(dp[2][i][j],dp[0][i - 1][j] - a[i]);
			dp[2][i][j] = max(dp[2][i][j],dp[1][i - 1][j] + a[i]);
			dp[3][i][j] = dp[3][i - 1][j];
			//新开
			dp[0][i][j] = max(dp[0][i][j],dp[2][i - 1][j - 1] + a[i]);
			dp[1][i][j] = max(dp[1][i][j],dp[2][i - 1][j - 1] - a[i]);
			dp[2][i][j] = max(dp[2][i][j],dp[2][i - 1][j - 1]);
			dp[3][i][j] = max(dp[3][i][j],dp[2][i - 1][j - 1]);
			//cout << dp[2][i][j] << " ";
		}
	//	cout << endl;
	}
	for(int i = n; i >= 1; i --)
	{
		cout << dp[2][n][i] - 1 << endl;
	}
}
signed main()
{
    IOS;
    int t = 1;//cin>>t;
    while(t--) solve();
}