/*
author : PakinDioxide
created : 09/05/2025 15:14
task : JOI18_candies
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 2e5+5;
ll n, a[mxN], dp[mxN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
priority_queue <tuple <ll, int, int, int>> q;
q.emplace(a[1], 1, 1, 1);
while (!q.empty()) {
auto [w, idx, cnt, t] = q.top(); q.pop();
dp[cnt] = max(dp[cnt], w);
if (idx == n) continue;
q.emplace(w + a[idx+1] - t*a[idx], idx+1, cnt+1-t, 1);
q.emplace(w, idx+1, cnt, 0);
}
for (int i = 1; i <= ceil(n/2.0); i++) cout << dp[i] << '\n';
}
