#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<ll> vi;
bool Mbe;

const int N = 2e5 + 5;
const ll inf = 1e14;

int n;
int a[N];

struct Mink {
	
	vector<ll> s;
	
	Mink () { }
	Mink (int n) { s.resize(n, -inf); }
	
	void emplace_back(ll x) {
		s.eb(x);
	}
	
	int size() {
		return (int)s.size();
	}
	
	ll& operator [](const int &r) {
		return s[r];
	}
	
	vi::iterator begin() {
		return s.begin();
	}
	
	vi::iterator end() {
		return s.end();
	}
	
	Mink shr() {
		Mink res(1);
		F (i, 0, (int)s.size() - 2) {
			res.eb(s[i]);
		}
		return res;
	}
	
	friend Mink operator + (Mink L, Mink R) {
		if (!L.size()) {
			return R;
		}
		if (!R.size()) {
			return L;
		}
		int sl = L.size(), sr = R.size();
		Mink res = Mink(sl + sr - 1);
		res[0] = L[0] + R[0];
		R (i, sl - 1, 1) {
			L[i] -= L[i - 1];
		}
		R (i, sr - 1, 1) {
			R[i] -= R[i - 1];
		}
		merge(L.begin() + 1, L.end(), R.begin() + 1, R.end(), res.begin() + 1, greater<int> ());
		F (i, 1, sl + sr - 2) {
			res[i] += res[i - 1];
		}
		return res;
	}
	
	friend Mink max(Mink L, Mink R) {
		int sl = L.size(), sr = R.size();
		Mink res(max(sl, sr));
		F (i, 0, max(sl, sr) - 1) {
			if (i < sl) {
				res[i] = max(res[i], L[i]);
			}
			if (i < sr) {
				res[i] = max(res[i], R[i]);
			}
		}
		return res;
	}
	
};

struct Info {
	
	Mink s[3][3];
	
	Info () { }
	Info (int w) {
		F (i, 0, 2) {
			F (j, 0, 2) {
				s[i][j] = Mink(2);
			}
		}
		s[0][0][1] = 0;
		s[0][1][0] = s[1][0][0] = w;
		s[0][2][0] = s[2][0][0] = -w;
	}
	
	Mink* operator [](const int &r) {
		return s[r];
	}
	
	friend Info operator + (Info L, Info R) {
		Info res;
		F (i, 0, 2) {
			F (j, 0, 2) {
				res[i][j] = max(res[i][j], L[i][j]);
				res[i][j] = max(res[i][j], R[i][j]);
				res[i][j] = max(res[i][j], L[i][0] + R[0][j]);
				res[i][j] = max(res[i][j], (L[i][1] + R[2][j]).shr());
				res[i][j] = max(res[i][j], (L[i][2] + R[1][j]).shr());
			}
		}
		return res;
	}
	
};

Info conq(int l, int r) {
	if (l == r) {
		return Info(a[l]);
	}
	int mid = (l + r) >> 1;
	return conq(l, mid) + conq(mid + 1, r);
}

void solve() {
	cin >> n;
	F (i, 1, n) {
		cin >> a[i];
	}
	Mink res = conq(1, n)[0][0];
	F (i, 1, n) {
		cout << res[i] << '\n';
	}
}

bool Med;
int main() {
	// FIO("");
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}