#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> v(n);
for(int i = 0; i < n; i++)
cin >> v[i];
auto merge = [](const vector<ll>& a, const vector<ll>& b) {
vector<ll> res{a[0]+b[0]};
int ai = 0, bi = 0;
while(ai+1 < sz(a) && bi+1 < sz(b)) {
if(a[ai+1]+b[bi] >= a[ai]+b[bi+1]) {
res.push_back(a[ai+1]+b[bi]);
ai++;
}
else {
res.push_back(a[ai]+b[bi+1]);
bi++;
}
}
while(ai+1 < sz(a)) {
res.push_back(a[ai+1]+b[bi]);
ai++;
}
while(bi+1 < sz(b)) {
res.push_back(a[ai]+b[bi+1]);
bi++;
}
return res;
};
auto update = [](vector<ll>& a, const vector<ll>& b) {
for(int i = 0; i < sz(b); i++) {
if(i < sz(a))
a[i] = max(a[i], b[i]);
else
a.push_back(b[i]);
}
};
function<vector<vector<ll>>(int, int)> solve = [&](int l, int r) {
if(l == r) {
return vector{vector<ll>{0}, vector<ll>{0}, vector<ll>{0}, vector<ll>{0, v[l]}};
}
int m = (l+r)/2;
auto left = solve(l, m);
auto right = solve(m+1, r);
vector<vector<ll>> res(4, vector<ll>());
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if((i&1) && (j&2))
continue;
int newMask = (i&2)+(j&1);
update(res[newMask], merge(left[i], right[j]));
}
}
return res;
};
auto res = solve(0, n-1);
vector<ll> ans;
for(int i = 0; i < 4; i++)
update(ans, res[i]);
for(int i = 1; i <= (n+1)/2; i++)
cout << ans[i] << "\n";
}
