#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long ll;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 2e5 + 25;
ll a[MAXN], n;
vector <ll> tree[MAXN << 2][2][2];
vector <ll> merge (vector <ll> x, vector <ll> y) {
vector <ll> ret((int)x.size() + (int)y.size() - 1, 0);
int g = 0, h = 0;
ret[0] = x[0] + y[0];
while (g + 1 < (int)x.size() && h + 1 < (int)y.size()) {
if (x[g + 1] + y[h] > x[g] + y[h + 1]) {
g++;
} else {
h++;
}
ret[g + h] = x[g] + y[h];
}
while (g + 1 < (int)x.size()) {
g++; ret[g + h] = x[g] + y[h];
}
while (h + 1 < (int)y.size()) {
h++; ret[g + h] = x[g] + y[h];
}
return ret;
}
vector <ll> mx (vector <ll> x, vector <ll> y) {
vector <ll> ret(max(x.size(), y.size()), 0);
for (int i = 0; i < (int)x.size(); i++) {
ret[i] = max(ret[i], x[i]);
}
for (int i = 0; i < (int)y.size(); i++) {
ret[i] = max(ret[i], y[i]);
}
return ret;
}
void recurse (int l, int r, int node) {
if (l == r) {
tree[node][0][0] = {0};
tree[node][0][1] = {0};
tree[node][1][0] = {0};
tree[node][1][1] = {0, a[l]};
return;
}
recurse(l, mid, tl);
recurse(mid + 1, r, tr);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
auto g = merge(tree[tl][i][0], tree[tr][0][j]);
auto h = merge(tree[tl][i][1], tree[tr][0][j]);
auto k = merge(tree[tl][i][0], tree[tr][1][j]);
tree[node][i][j] = mx(g, h);
tree[node][i][j] = mx(tree[node][i][j], k);
}
}
}
void solve () {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
recurse(1, n, 1);
for (int i = 1; i <= (n + 1) / 2; i++) {
ll mx = 0;
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
if ((int)tree[1][j][k].size() > i) {
mx = max(mx, tree[1][j][k][i]);
}
}
}
cout << mx << '\n';
}
}
signed main () {
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
