#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false
const int MAXN = 200 * 1000 + 17;
const ll INF = ll(-1000 * 1000 * 1000) * ll(1000 * 1000 * 1000);
ll a[MAXN];
vector<ll> lacz (vector<ll> v1, vector<ll> v2) {
int n1 = int(v1.size());
int n2 = int(v2.size());
vector<ll> v = {};
int i1 = 0, i2 = 0;
for (int i = 0; i < n1 + n2; i ++) {
if (i1 == n1) {
v.pb(v2[i2]);
i2 ++;
continue;
}
if (i2 == n2) {
v.pb(v1[i1]);
i1 ++;
continue;
}
if (v1[i1] > v2[i2]) {
v.pb(v1[i1]);
i1 ++;
} else {
v.pb(v2[i2]);
i2 ++;
}
}
return v;
}
int koduj (int x, int y) {
return (x * 2 + y);
}
vector<vector<ll>> dziel (int P, int K) {
if (P == K) {
return {{INF}, {INF}, {INF}, {a[P]}};
}
int sr = (P + K)/ 2;
vector<vector<ll>> l = dziel(P, sr);
vector<vector<ll>> r = dziel(sr + 1, K);
vector<vector<ll>> wyn = {};
int n = (K - P + 2)/ 2;
for (int i = 0; i < 4; i ++) {
wyn.pb({});
for (int j = 0; j < n; j ++) {
wyn.back().pb(INF);
}
}
for (int i = 0; i < 2; i ++) {
for (int j = 0; j < 2; j ++) {
ll s1 = 0, s2 = 0;
ll poprz = 0;
for (int k = 0; k < int(l[koduj(i, j)].size()); k ++) {
s1 += wyn[koduj(i, 0)][k];
s2 += l[koduj(i, j)][k];
s1 = max(s1, INF);
s2 = max(s2, INF);
ll s = max(s1, s2);
if (s > 0) {
wyn[koduj(i, 0)][k] = s - poprz;
}
poprz = s;
}
}
}
for (int i = 0; i < 2; i ++) {
for (int j = 0; j < 2; j ++) {
ll s1 = 0, s2 = 0;
ll poprz = 0;
for (int k = 0; k < int(r[koduj(i, j)].size()); k ++) {
s1 += wyn[koduj(0, j)][k];
s2 += r[koduj(i, j)][k];
s1 = max(s1, INF);
s2 = max(s2, INF);
ll s = max(s1, s2);
if (s > 0) {
wyn[koduj(0, j)][k] = s - poprz;
}
poprz = s;
}
}
}
for (int i = 0; i < 2; i ++) {
for (int j = 0; j < 2; j ++) {
for (int k = 0; k < 2; k ++) {
if (j == 1 && k == 1) {
continue;
}
for (int m = 0; m < 2; m ++) {
vector<ll> akt = lacz(l[koduj(i, j)], r[koduj(k, m)]);
ll s1 = 0, s2 = 0;
ll poprz = 0;
for (int ii = 0; ii < min(n, int(akt.size())); ii ++) {
s1 += wyn[koduj(i, m)][ii];
s2 += akt[ii];
s1 = max(s1, INF);
s2 = max(s2, INF);
ll s = max(s1, s2);
if (s > 0) {
wyn[koduj(i, m)][ii] = s - poprz;
}
poprz = s;
}
}
}
}
}
/*cout << P << " " << K << "\n";
for (int i = 0; i < 4; i ++) {
for (auto x : l[i]) {
cout << x << " ";
}
cout << "\n";
}
cout << "\n";
for (int i = 0; i < 4; i ++) {
for (auto x : r[i]) {
cout << x << " ";
}
cout << "\n";
}
cout << "\n";
for (int i = 0; i < 4; i ++) {
for (auto x : wyn[i]) {
cout << x << " ";
}
cout << "\n";
}
cout << "\n";*/
return wyn;
}
int main () {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> a[i];
}
vector<vector<ll>> wyn = dziel(0, n - 1);
ll s = 0;
for (int i = 0; i < (n + 1)/ 2; i ++) {
s += max({wyn[0][i], wyn[1][i], wyn[2][i], wyn[3][i]});
cout << s << "\n";
}
return 0;
}
