#include <bits/stdc++.h>
using namespace std;
#define int long long
#define viii vector <vector <vector <int> > >
const int NM = 2e5, inf = 1e18;
int n, a[NM+5];
int res[NM/2+5][2][2], tmp[NM/2+5];
void process(int l, int r, int j, int k, int nj, int nk, viii &f, viii &g){
int cur = 0;
tmp[0] = 0;
for (int i = 1; i <= (r-l+2)/2; i++){
while (cur+1 <= i){
int val1 = f[cur][j][nj]+g[i-cur][nk][k], val2 = f[cur+1][j][nj]+g[i-cur-1][nk][k];
if (val1 < 0) val1 = -inf;
if (val2 < 0) val2 = -inf;
if (val1 <= val2) cur++;
else break;
}
tmp[i] = f[cur][j][nj]+g[i-cur][nk][k];
}
}
void dnc(int l, int r){
if (l == r){
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++){
res[0][i][j] = 0;
if (i&j) res[1][i][j] = a[l]; else res[1][i][j] = -inf;
}
return;
}
int mid = (l+r)/2;
dnc(l, mid);
vector <vector <vector <int> > > f((r-l+2)/2+1), g((r-l+2)/2+1);
for (int i = 0; i <= (r-l+2)/2; i++){
f[i].resize(2, vector <int>(2));
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
f[i][j][k] = (i <= (mid-l+2)/2 ? res[i][j][k] : -inf);
}
dnc(mid+1, r);
for (int i = 0; i <= (r-l+2)/2; i++){
g[i].resize(2, vector <int>(2));
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
g[i][j][k] = (i <= (r-mid+1)/2 ? res[i][j][k] : -inf);
}
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++){
process(l, r, j, k, 0, 1, f, g);
for (int i = 0; i <= (r-l+2)/2; i++)
res[i][j][k] = tmp[i];
process(l, r, j, k, 1, 0, f, g);
for (int i = 0; i <= (r-l+2)/2; i++)
res[i][j][k] = max(res[i][j][k], tmp[i]);
for (int i = 0; i <= (r-l+2)/2; i++)
for (int nj = 0; nj < 2; nj++)
for (int nk = 0; nk < 2; nk++)
if (nj <= j && nk <= k) res[i][j][k] = max(res[i][j][k], res[i][nj][nk]);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
dnc(1, n);
for (int i = 1; i <= (n+1)/2; i++)
cout << res[i][1][1] << '\n';
return 0;
}
