#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

ll n, m, type, a[maxn];

typedef vector<ll> poly;

inline poly operator + (poly a, poly b) {
	int n = (int)a.size() - 1, m = (int)b.size() - 1;
	poly res;
	res.pb(a[0] + b[0]);
	int i = 0, j = 0;
	ll s = a[0] + b[0];
	while (i < n && j < m) {
		if (a[i + 1] - a[i] > b[j + 1] - b[j]) {
			s += a[i + 1] - a[i];
			++i;
			res.pb(s);
		} else {
			s += b[j + 1] - b[j];
			++j;
			res.pb(s);
		}
	}
	while (i < n) {
		s += a[i + 1] - a[i];
		++i;
		res.pb(s);
	}
	while (j < m) {
		s += b[j + 1] - b[j];
		++j;
		res.pb(s);
	}
	assert((int)res.size() == n + m + 1);
	return res;
}

inline poly get(poly a, poly b) {
	int n = (int)a.size(), m = (int)b.size();
	poly res(max(n, m), -inf);
	for (int i = 0; i < max(n, m); ++i) {
		if (i < n) {
			res[i] = max(res[i], a[i]);
		}
		if (i < m) {
			res[i] = max(res[i], b[i]);
		}
	}
	return res;
}

poly F[262199][3][3];

void dfs(int rt, int l, int r) {
	if (l == r) {
		F[rt][0][0] = {-inf};
		F[rt][0][1] = {-a[l]};
		F[rt][0][2] = {-inf};
		F[rt][1][0] = {-a[l]};
		F[rt][1][1] = {0, 0};
		F[rt][1][2] = {a[l]};
		F[rt][2][0] = {-inf};
		F[rt][2][1] = {a[l]};
		F[rt][2][2] = {-inf};
		return;
	}
	int mid = (l + r) >> 1;
	dfs(rt << 1, l, mid);
	dfs(rt << 1 | 1, mid + 1, r);
	for (int i = 0; i <= 2; ++i) {
		for (int j = 0; j <= 2; ++j) {
			F[rt][i][j] = get(F[rt << 1][i][j], F[rt << 1 | 1][i][j]);
			poly res = F[rt << 1][i][1] + F[rt << 1 | 1][1][j];
			F[rt][i][j] = get(F[rt][i][j], res);
			res = F[rt << 1][i][0] + F[rt << 1 | 1][2][j];
			res.insert(res.begin(), -inf);
			F[rt][i][j] = get(F[rt][i][j], res);
			res = F[rt << 1][i][2] + F[rt << 1 | 1][0][j];
			res.insert(res.begin(), -inf);
			F[rt][i][j] = get(F[rt][i][j], res);
		}
	}
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	dfs(1, 1, n);
	for (int i = 1; i <= n; ++i) {
		printf("%lld\n", F[1][1][1][i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}