#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
ll n, A[MAXN];
vector<ll> merge_divide(vector<ll> a, vector<ll> b) {
vector<ll> ans;
int ap = 0, bp = 0, as = a.size(), bs = b.size();
ll f = 0;
ans.push_back(f);
while (ap + 1 < as || bp + 1 < bs) {
if (ap + 1 >= as || (bp + 1 < bs && a[ap + 1] - a[ap] < b[bp + 1] - b[bp])) {
f += b[bp + 1] - b[bp];
bp++;
} else {
f += a[ap + 1] - a[ap];
ap++;
}
ans.push_back(f);
}
return ans;
}
vector<ll> merge_max(vector<ll> a, vector<ll> b) {
while (a.size() < b.size()) a.push_back(0);
while (b.size() < a.size()) b.push_back(0);
for (int i = 0; i < int(a.size()); i++)
a[i] = max(a[i], b[i]);
return a;
}
vector<vector<ll>> solve(int l, int r) {
if (l == r) return {{0}, {0}, {0}, {0, A[l]}};
int mid = (l + r) >> 1;
vector<vector<ll>> ans = {{0ll}, {0ll}, {0ll}, {0ll}},
A = solve(l, mid), B = solve(mid + 1, r);
for (int a = 0; a < 4; a++) {
for (int b = 0; b < 4; b++) {
if ((a & 2) > 0 && (b & 1) > 0) continue;
int c = (a & 1) | (b & 2);
ans[c] = merge_max(ans[c], merge_divide(A[a], B[b]));
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> A[i];
vector<ll> ans = solve(1, n)[3];
ans.erase(ans.begin());
for (ll e : ans)
cout << e << endl;
return 0;
}
