#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 2e18;
void upd(vector<ll> &a, const vector<ll> &b) {
if (a.size() < b.size()) {
a.resize(b.size(), -INF);
}
for (int i = 0; i < (int) b.size(); ++i) {
a[i] = max(a[i], b[i]);
}
}
void upd(vector<ll> &t, const vector<ll> &a, const vector<ll> &b) {
int sz_a = a.size(), sz_b = b.size();
int mn_a = 0;
while (mn_a < sz_a && a[mn_a] == -INF) {
++mn_a;
}
if (mn_a == sz_a) return;
int mx_a = mn_a;
while (mx_a + 1 < sz_a && a[mx_a + 1] != -INF) {
++mx_a;
}
int mn_b = 0;
while (mn_b < sz_b && b[mn_b] == -INF) {
++mn_b;
}
if (mn_b == sz_b) return;
int mx_b = mn_b;
while (mx_b + 1 < sz_b && b[mx_b + 1] != -INF) {
++mx_b;
}
vector<ll> da, db;
for (int i = mn_a + 1; i <= mx_a; ++i) {
da.push_back(a[i] - a[i - 1]);
}
for (int i = mn_b + 1; i <= mx_b; ++i) {
db.push_back(b[i] - b[i - 1]);
}
vector<ll> d(da.size() + db.size());
merge(da.begin(), da.end(), db.begin(), db.end(), d.begin(), greater<ll>());
vector<ll> c(mx_a + mx_b + 1, -INF);
c[mn_a + mn_b] = a[mn_a] + b[mn_b];
for (int i = 0; i < mx_a - mn_a + mx_b - mn_b; ++i) {
c[mn_a + mn_b + i + 1] = c[mn_a + mn_b + i] + d[i];
}
if (t.size() < c.size()) {
t.resize(c.size(), -INF);
}
for (int i = 0; i < (int) c.size(); ++i) {
t[i] = max(t[i], c[i]);
}
}
const int N = 2e5 + 7;
typedef array<array<vector<ll>, 2>, 2> Res;
Res merge(const Res &a, const Res &b) {
Res c;
for (int al = 0; al < 2; ++al) {
for (int ar = 0; ar < 2; ++ar) {
for (int bl = 0; bl < 2 - ar; ++bl) {
for (int br = 0; br < 2; ++br) {
upd(c[al][br], a[al][ar], b[bl][br]);
}
}
}
}
return c;
}
int n;
ll a[N];
Res solve(int l, int r) {
if (r - l == 1) {
Res res;
res[0][0].resize(1, -INF);
res[0][0][0] = 0;
res[1][1].resize(2, -INF);
res[1][1][1] = a[l];
return res;
}
int mid = (l + r) / 2;
return merge(solve(l, mid), solve(mid, r));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
auto res = solve(0, n);
vector<ll> ans((n + 1) / 2 + 1, -INF);
for (int l = 0; l < 2; ++l) {
for (int r = 0; r < 2; ++r) {
upd(ans, res[l][r]);
}
}
for (int i = 1; i <= (n + 1) / 2; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
