#include <bits/stdc++.h>
using namespace std;
template<typename T>
using V = vector<T>;
#define f first
#define s second
#define F0R(i,n) for(ll i = 0; i < n;i++)
#define FOR(i,j,n) for(ll i = j; i < n;i++)
using ll = long long;
constexpr ll INF = 1e15;
using vi = V<ll>;
vi arr;
vi combine(vi a, vi b, ll targetSize) {
a.resize(targetSize, -INF);
b.resize(targetSize, -INF);
vi c(targetSize, -INF);
int l = 0, r = 0;
F0R(i, targetSize) {
c[i] = a[l] + b[r];
if (a[l + 1]- a[l] > b[r + 1] - b[r]) {
l++;
} else
r++;
}
return c;
}
V<V<vi>> solve(ll l, ll 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;
}
ll 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);
ll 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);
ll 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) {
ll best = 0;
F0R(j, 2) {
F0R(k, 2) {
best = max(best, res[j][k][i]);
}
}
cout << best << "\n";
}
return 0;
}
