#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
	int x = 0; char c = getchar();
	while(!isdigit(c))c = getchar();
	do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
	return x;
}
const int maxn = 2e5 + 55, inf = 0x3f3f3f3f;

int n, a[maxn];
struct node{
	vector<ll>f[3][3];
	void init(int x){
		f[2][0].push_back(-x); f[0][2].push_back(-x);
		f[1][0].push_back(x);  f[0][1].push_back(x);
		f[0][0].push_back(0);  f[0][0].push_back(0);
	}
};
void cf(vector<ll>&x){for(int i = x.size() - 1; i > 0; --i)x[i] -= x[i - 1];}
void sum(vector<ll>&x){for(int i = 1; i < x.size(); ++i)x[i] += x[i - 1];}
void ckmx(vector<ll>&x,const vector<ll>&y){
	while(x.size() < y.size())x.push_back(-inf);
	for(int i = 0; i < y.size(); ++i)if(y[i] > x[i])x[i] = y[i];
}
vector<ll>merge(vector<ll>&x, vector<ll>&y, int type){
	vector<ll>tmp;
	int px = 1, py = 1; 
	if(type)tmp.push_back(0);
	tmp.push_back(x[0] + y[0]);
	while(px < x.size() && py < y.size()){
		if(x[px] > y[py])tmp.push_back(x[px++]);
		else tmp.push_back(y[py++]);
	}
	while(px < x.size())tmp.push_back(x[px++]);
	while(py < y.size())tmp.push_back(y[py++]);
	sum(tmp); tmp[0] = -inf; return tmp;
}
node solve(int l, int r){
	node f;
	if(l == r){f.init(a[l]); return f;}
	int mid = (l + r) >> 1; 
	node L = solve(l, mid), R = solve(mid + 1, r);
	for(int i = 0; i < 3; ++i)
		for(int j = 0; j < 3; ++j){
			ckmx(f.f[i][j], L.f[i][j]); cf(L.f[i][j]);
			ckmx(f.f[i][j], R.f[i][j]); cf(R.f[i][j]);
		}
	for(int i = 0; i < 3; ++i)
		for(int j = 0; j < 3; ++j){
			ckmx(f.f[i][j], merge(L.f[i][0], R.f[0][j], 0));
			if(L.f[i][1].size() && R.f[2][j].size())ckmx(f.f[i][j], merge(L.f[i][1], R.f[2][j], 1));
			if(L.f[i][2].size() && R.f[1][j].size())ckmx(f.f[i][j], merge(L.f[i][2], R.f[1][j], 1));
		}
	return f;
}

int main(){
	n = read();
	for(int i = 1; i <= n; ++i)a[i] = read();
	node ans = solve(1, n);
	for(int i = 1; i <= n; ++i)printf("%lld\n",ans.f[0][0][i]);	
	return 0;
}