#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <iterator>
#include <set>
#include <random>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <stack>
#include <numeric>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll md1 = 1'000'000'007;
const ll md2 = 998244353;
const ll mdd = 666013;
ll ask(int l, int r) {
cout << "? " << l + 1 << " " << r << endl;
ll v;
cin >> v;
return v;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
priority_queue<pair<ll, pair<int, pair<int, int>>>> q;
vector<int> l(n), r(n);
vector<ll> prof = a;
vector<int> it(n);
iota(it.begin(), it.end(), 0);
iota(l.begin(), l.end(), 0);
iota(r.begin(), r.end(), 1);
for (int i = 0; i < n; i++)
q.push({ a[i], { i, {l[i], r[i]} } });
ll ans = 0;
for (int I = 0; I < (n + 1) / 2; I++) {
while (true) {
auto nw = q.top();
q.pop();
if (nw.second.second.first != l[nw.second.first] || nw.second.second.second != r[nw.second.first])
continue;
int i = nw.second.first;
ans += nw.first;
cout << ans << "\n";
a[i] += prof[i];
prof[i] *= -1;
if (l[i]) {
int ww = it[l[i] - 1];
l[i] = l[ww];
r[ww] = -1;
l[ww] = -1;
it[l[i]] = i;
a[i] += a[ww];
prof[i] += prof[ww];
}
if (r[i] < n) {
int ww = it[r[i]];
r[i] = r[ww];
l[ww] = -1;
r[ww] = -1;
it[r[i] - 1] = i;
a[i] += a[ww];
prof[i] += prof[ww];
}
q.push({ prof[i], {i, {l[i], r[i]}} });
break;
}
}
}
return 0;
}
