#include <bits/stdc++.h>
#define ll long long
const int MAX=1e4+10;
int n, dp[MAX][MAX][4], a[MAX];
using std::max;
int main() {
	scanf("%d", &n);	
	for (int i=1;i<=n;i++) scanf("%d", &a[i]);
	memset(dp, -0x3f, sizeof(dp));
	dp[0][0][3]=0;
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) {
		dp[i][j][0]=max(dp[i-1][j-1][3], dp[i-1][j][0]);
		dp[i][j][1]=max({dp[i-1][j-1][3]+a[i], dp[i-1][j][0]+a[i], dp[i-1][j][1]});
		dp[i][j][2]=max({dp[i-1][j-1][3]-a[i], dp[i-1][j][0]-a[i], dp[i-1][j][2]});
		dp[i][j][3]=max({dp[i-1][j-1][3], dp[i-1][j][3], dp[i-1][j][1]-a[i], dp[i-1][j][2]+a[i]});
	}
//	for (int i=1;i<=n;i++) {
//		for (int j=1;j<=n;j++) {
//			for (int k=0;k<=3;k++) printf("%d!", dp[i][j][k]);
//			puts("\n===");
//		}
//		putchar('\n');
//	}
	for (int i=1;i<=n;i++) printf("%d\n", dp[n][i][3]); 
	return 0;
}