#include "bits/stdc++.h"
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
struct DP {
vector<ll> t[2][2];
DP() {
t[0][0] = t[0][1] = t[1][0] = t[1][1] = vector<ll>{0LL};
}
};
vector<ll> max(vector<ll> a, const vector<ll> &b) {
for (int i = 0; i < ssize(b); ++i) {
if (i >= ssize(a)) a.eb(0);
a[i] = max(a[i], b[i]);
}
return a;
}
vector<ll> comb(const vector<ll> &a, const vector<ll> &b) {
vector<ll> res;
int i = 0, j = 0;
while (i < ssize(a) && j < ssize(b)) {
res.eb(a[i] + b[j]);
if (i == ssize(a) - 1)
++j;
else if (j == ssize(b) - 1)
++i;
else if (a[i+1] - a[i] > b[j+1] - b[j])
++i;
else
++j;
}
return res;
}
DP comb(const DP &a, const DP &b) {
DP ret;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
ret.t[i][j] = max(ret.t[i][j], comb(a.t[i][0], b.t[0][j]));
ret.t[i][j] = max(ret.t[i][j], comb(a.t[i][0], b.t[1][j]));
ret.t[i][j] = max(ret.t[i][j], comb(a.t[i][1], b.t[0][j]));
}
}
return ret;
}
DP solve(int l, int r, const vector<int> &a) {
if (l == r) {
DP res;
res.t[1][1].eb(a[l]);
return res;
}
int mid = (l + r) / 2;
DP dp_l = solve(l, mid, a), dp_r = solve(mid+1, r, a);
return comb(dp_l, dp_r);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
DP dp = solve(0, n-1, a);
for (int i = 1; i <= (n+1)/2; ++i) {
ll res = 0;
if (i < ssize(dp.t[0][0])) res = max(res, dp.t[0][0][i]);
if (i < ssize(dp.t[0][1])) res = max(res, dp.t[0][1][i]);
if (i < ssize(dp.t[1][0])) res = max(res, dp.t[1][0][i]);
if (i < ssize(dp.t[1][1])) res = max(res, dp.t[1][1][i]);
cout << res << '\n';
}
return 0;
}
