//Oh? You're Approaching Me?
#include <bits/stdc++.h>
//#include <fstream>
using namespace std;
//
#define int long long
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
// #pragma GCC optimize("O3,unroll-loops")
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define F first
#define S second
#define SZ(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define cl clear
#define endl '\n'
#define deb(x) cerr << #x << " = " << x << '\n'
#define dokme(x) {cout << x << endl; return;}
#define wtf cout << "[ahaaaaaaaaaaaaaaaa]" << endl;
const int maxn = 1e6 + 100;
const int mod = 998244353;
const int inf = 1e17 + 5;
const int LOG = 22;
#define mid ((l + r) / 2)
#define lc (id * 2)
#define rc (lc + 1)
//g++ main.cpp -o main && main.exe
int a[maxn];
vector<ll> dp[2][2][maxn];
void divide(int id, int l, int r) {
if (l + 1 == r) {
dp[0][0][id] = {0};
dp[0][1][id] = {0};
dp[1][0][id] = {0};
dp[1][1][id] = {0, a[l]};
return;
}
divide(lc, l, mid);
divide(rc, mid, r);
for(int i = 0; i < 4; i++){
dp[i >> 1 & 1][i & 1][id].resize(1, 0);
dp[i >> 1 & 1][i & 1][id].resize(r - l + 1, -inf);
}
for (int ml = 0; ml < 4; ml++) {
for (int mr = 0; mr < 4; mr++) {
int l1 = ml >> 1 & 1, r1 = ml & 1, l2 = mr >> 1 & 1, r2 = mr & 1;
if (r1 + l2 > 1)
continue;
int pl = 0, pr = 0;
vector<ll> &pdl = dp[l1][r1][lc];
vector<ll> &pdr = dp[l2][r2][rc];
while ((pl + 1 < SZ(pdl)) || (pr + 1 < SZ(pdr))) {
if (pl + 1 == SZ(pdl))
pr++;
else if (pr + 1 == SZ(pdr))
pl++;
else {
if (pdl[pl + 1] - pdl[pl] >= pdr[pr + 1] - pdr[pr])
pl++;
else
pr++;
}
dp[l1][r2][id][pl + pr] = max(dp[l1][r2][id][pl + pr], pdl[pl] + pdr[pr]);
}
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
dp[i][j][lc].clear();
dp[i][j][rc].clear();
}
}
}
signed main() {
migmig;
int n; cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
divide(1, 1, n + 1);
for (int i = 1; i <= ((n + 1) / 2); i++) {
ll ans = -inf;
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
ans = max(ans, dp[a][b][1][i]);
}
}
cout << ans << '\n';
}
}
