#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using State = array<array<vector<ll>, 2>, 2>;
vector<ll> merge(const vector<ll> &lf, const vector<ll> &rg) {
if (lf.empty()) return rg;
if (rg.empty()) return lf;
deque<ll> lfd;
deque<ll> rgd;
for (int i = 0; i + 1 < int(lf.size()); ++i) {
lfd.emplace_back(lf[i + 1] - lf[i]);
}
for (int i = 0; i + 1 < int(rg.size()); ++i) {
rgd.emplace_back(rg[i + 1] - rg[i]);
}
vector<ll> ans = {lf[0] + rg[0]};
while (lfd.size() && rgd.size()) {
if (lfd.front() > rgd.front()) {
ans.emplace_back(ans.back() + lfd.front());
lfd.pop_front();
} else {
ans.emplace_back(ans.back() + rgd.front());
rgd.pop_front();
}
}
while (lfd.size()) {
ans.emplace_back(ans.back() + lfd.front());
lfd.pop_front();
}
while (rgd.size()) {
ans.emplace_back(ans.back() + rgd.front());
rgd.pop_front();
}
return ans;
}
void optimize(vector<ll> &x, const vector<ll> &y) {
while (x.size() < y.size()) {
x.emplace_back(0ll);
}
for (int i = 0; i < int(y.size()); ++i) {
x[i] = max(x[i], y[i]);
}
}
State merge(const State &lf, const State &rg) {
State ans = {};
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
for (int l = 0; l < 2; ++l) {
if (!j || !k) {
optimize(ans[i][l], merge(lf[i][j], rg[k][l]));
}
}
}
}
}
return ans;
}
void modify(State &s) {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
if (i) optimize(s[i][j], s[i - 1][j]);
if (j) optimize(s[i][j], s[i][j - 1]);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
int N;
cin >> N;
vector<ll> A(N);
for (int i = 0; i < N; ++i) cin >> A[i];
function<State(int, int)> solve = [&](int l, int r) {
State ans = {};
if (l == r) {
ans[0][0] = {0};
ans[1][1] = {0, A[l]};
} else {
int md = (l + r) >> 1;
ans = merge(solve(l, md), solve(md + 1, r));
}
modify(ans);
return ans;
};
auto ans = solve(0, N - 1);
for (int i = 1; i <= (N + 1) / 2; ++i) cout << ans[1][1][i] << "\n";
return 0;
}
