#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
const int maxn = 2e5 + 5;
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
int N;
ll a[maxn];
struct node {
ll val;
node *l, *r;
node () {
val = 0;
l = r = NULL;
}
};
using llp = pair<ll, node*>;
multiset<ii> Q;
int le[maxn], ri[maxn];
int main(int argc, char const *argv[])
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> a[i];
le[i] = i-1, ri[i] = i+1;
Q.insert(ii(a[i], i));
}
a[0] = -1e18, a[N+1] = -1e18;
/*for(int i = 1; i <= N; i++) {
node *now = new node();
now -> val = a[i];
now -> l = prev;
if(prev) now -> l -> r = now;
Q.insert(llp(a[i], now));
prev = now;
}*/
ll ans = 0;
for(int i = 1; i <= (N - 1) / 2 + 1; i++) {
// take best
int best = (int)Q.rbegin() -> second;
Q.erase(--Q.end());
// update answer
// ans += best -> val;
ans += a[best];
// create virtual elem
// node *now = new node();
// now -> val = -best -> val;
a[best] = -a[best];
int l = le[best];
int r = ri[best];
if(true) {
Q.erase(ii(a[l], l));
le[best] = le[l];
a[best] += a[l];
}
if(true) {
Q.erase(ii(a[r], r));
ri[best] = ri[r];
a[best] += a[r];
}
if(le[best]) {
ri[le[best]] = best;
}
if(ri[best] <= N) {
le[ri[best]] = best;
}
/*if(best -> l) {
Q.erase(llp(best -> l -> val, best -> l));
now -> val += best -> l -> val;
now -> l = best -> l -> l;
// delete(best -> l);
} else {
flag = 0;
}
if(best -> r) {
Q.erase(llp(best -> r -> val, best -> r));
now -> val += best -> r -> val;
now -> r = best -> r -> r;
// delete(best -> r);
} else {
flag = 0;
}
if(now -> l) now -> l -> r = now;
if(now -> r) now -> r -> l = now;*/
Q.insert(ii(a[best], best));
cout << ans << endl;
}
return 0;
}
