#include <bits/stdc++.h>
using namespace std;
template<typename T>
using V = vector<T>;
using vi = V<int>;
#define f first
#define s second
#define F0R(i,n) for(int i = 0; i < n;i++)
#define FOR(i,j,n) for(int i = j; i < n;i++)
constexpr int INF = 1e9;
vi arr;
vi combine(vi a, vi b, int targetSize) {
a.resize(targetSize);
b.resize(targetSize);
vi c(targetSize);
F0R(i, targetSize) {
F0R(j, i + 1) {
c[i] = max(c[i], a[j] + b[i - j]);
}
}
return c;
}
V<V<vi>> solve(int l, int r) {
V<V<vi>> ans(2, V<vi>(2, vi(r - l + 1, -INF)));
if (r - l <= 1) {
ans[0][0][0] = 0;
ans[1][1][1] = arr[l];
return ans;
}
int mid = (l + r) / 2;
V<V<vi>> left = solve(l, mid), right = solve(mid, r);
F0R(i, 2) {
F0R(j, 2) {
F0R(k, 2) {
F0R(t, 2) {
if (k & t) continue;
vi res = combine(left[i][k], right[t][j], r - l + 1);
int iter = 0;
for (auto &v : ans[i][j])
v = max(v, res[iter++]);
}
}
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
arr.resize(n);
F0R(i, n)
cin >> arr[i];
V<V<vi>> res = solve(0, n);
FOR(i, 1, ((n + 1) / 2) + 1) {
int best = 0;
F0R(j, 2) {
F0R(k, 2) {
best = max(best, res[j][k][i]);
}
}
cout << best << "\n";
}
return 0;
}
