#include <bits/stdc++.h>
using namespace std;
/*input
5
3
5
1
7
6
*/
/*input
20
623239331
125587558
908010226
866053126
389255266
859393857
596640443
60521559
11284043
930138174
936349374
810093502
521142682
918991183
743833745
739411636
276010057
577098544
551216812
816623724
*/
long long a[200'000];
struct rez {
// 0 - not included
// 1 - might be included
vector<long long> v[2][2];
};
rez rek(int pr, int pab) {
if (pr >= pab)
return rez{{{{0}, {0}}, {{0}, {0}}}};
if (pr + 1 == pab) {
rez r{{{{0}, {0}}, {{0}, {0, a[pr]}}}};
return r;
}
int mi = (pr + pab) / 2;
auto v = rek(pr, mi);
auto w = rek(mi, pab);
rez r;
int n = (pab - pr + 1) / 2;
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
if (r.v[x][y].empty()) {
r.v[x][y].push_back(0);
}
for (int t = 0; t < 2; ++t) {
int vi = 0, wi = 0;
for (int i = 1; i <= n; ++i) {
if (vi + 1 < (long long)v.v[x][t].size()) {
vi++;
}
else if (wi + 1 < (long long)w.v[1 - t][y].size()) {
wi++;
}
else {
break;
}
if (i >= (long long)r.v[x][y].size()) {
r.v[x][y].push_back(0);
}
long long dab = v.v[x][t][vi] + w.v[1 - t][y][wi];
while (vi > 0 and wi + 1 < (long long)w.v[1 - t][y].size() and v.v[x][t][vi - 1] + w.v[1 - t][y][wi + 1] > dab) {
vi--;
wi++;
dab = v.v[x][t][vi] + w.v[1 - t][y][wi];
}
while (wi > 0 and vi + 1 < (long long)v.v[x][t].size() and v.v[x][t][vi + 1] + w.v[1 - t][y][wi - 1] > dab) {
vi++, wi--;
dab = v.v[x][t][vi] + w.v[1 - t][y][wi];
}
r.v[x][y][i] = max(r.v[x][y][i], dab);
}
}
}
}
return r;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
auto r = rek(0, n);
// for (int x = 0; x < 2; ++x) {
// for (int y = 0; y < 2; ++y) {
// cout << x << " " << y << endl << " ";
// for (int i = 0; i < (long long)r.v[x][y].size(); ++i) {
// cout << r.v[x][y][i] << " ";
// }
// cout << endl;
// }
// }
for (int i = 1; i <= (n + 1) / 2; ++i) {
long long ma = 0;
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
if (i < (long long)r.v[x][y].size()) {
ma = max(ma, r.v[x][y][i]);
}
}
}
cout << ma << "\n";
}
}
