#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)
mt19937 rng;
vector<ll> merge(vector<ll> a, vector<ll> b) {
if (a.empty() || b.empty()) return {};
int i = 1, j = 1;
vector<ll> res = {a[0] + b[0]};
while (i < sz(a) || j < sz(b)) {
if (j == sz(b) || i < sz(a) && a[i] - a[i - 1] > b[j] - b[j - 1]) {
res.pb(a[i] - a[i - 1] + res[sz(res) - 1]);
i++;
} else {
res.pb(b[j] - b[j - 1] + res[sz(res) - 1]);
j++;
}
}
return res;
}
vector<ll> vMax(vector<ll> a, vector<ll> b) {
for (int i = 0; i < sz(b); i++) {
if (sz(a) == i) a.pb(LLONG_MIN);
a[i] = max(a[i], b[i]);
}
return a;
}
vector<vector<vector<ll>>> search(vector<int> a) {
if (sz(a) == 1) {
vector res(2, vector<vector<ll>>(2, {0}));
res[0][0].pb(a[0]);
return res;
}
int mid = sz(a) / 2;
vector<int> aL, aR;
for (int i = 0; i < mid; i++) aL.pb(a[i]);
for (int i = mid; i < sz(a); i++) aR.pb(a[i]);
auto left = search(aL), right = search(aR);
vector res(2, vector<vector<ll>>(2));
for (int l = 0; l < 2; l++) {
for (int r = 0; r < 2; r++) {
res[l][r] = vMax(res[l][r], merge(left[l][0], right[1][r]));
res[l][r] = vMax(res[l][r], merge(left[l][1], right[0][r]));
res[0][0] = vMax(res[0][0], res[l][r]);
}
}
vector<vector<vector<ll>>>().swap(left);
vector<vector<vector<ll>>>().swap(right);
return res;
}
void solve() {
int N; cin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++) cin >> a[i];
auto res = search(a);
for (int i = 1; i < sz(res[0][0]); i++) {
cout << res[0][0][i] << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
solve();
return 0;
}
