#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
int main() {
int n;
cin >> n;
ll ps[n + 4]{};
map<int, int> s;
multiset<pair<ll, int>> m;
auto calc = [&] (int l, int r) { return ps[r + 2] - ps[l] - (ps[r + 1] - ps[l + 1]); };
for (int i = 1; i <= n; ++i) {
cin >> ps[i + 2];
ps[i + 2] += ps[i];
s[i] = i;
m.emplace(calc(i, i), i);
}
ll ans = 0;
for (int k = 0; (k << 1) < n; ++k) {
cout << (ans += m.rbegin()->first) << endl;
int l = m.rbegin()->second;
m.erase(prev(m.end()));
auto it = s.find(l--);
int r = it->second + 1;
for (; next(it) != s.end(); s.erase(next(it))) {
auto [li, ri] = *next(it);
if (li > r) break;
m.erase({calc(li, r = ri), li});
}
for (; it != s.begin(); s.erase(prev(it))) {
auto [li, ri] = *prev(it);
if (ri < l) break;
m.erase({calc(l = li, ri), li});
}
s.erase(it);
s[l] = r;
if (l >= 1 and r <= n) m.emplace(calc(l, r), l);
}
}
