#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 2e5 + 7, INF = 1e18 + 7;
int a[N], d[N];
bool used[N];
struct Comp {
bool operator () (int i, int j) { return (d[i] > d[j]) || (d[i] == d[j] && i < j); };
};
set <int> s1; set <int, Comp> s2;
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) {
d[i] = a[i];
s1.insert(i); s2.insert(i);
}
int ans = 0;
for (int _ = 1; _ <= (n + 1) / 2; ++_) {
int i = *s2.begin(); s2.erase(s2.begin()); s1.erase(i);
ans += d[i]; cout << ans << '\n';
d[i] = -d[i];
auto r = s1.upper_bound(i);
bool c = 1;
if (r != s1.end()) {
d[i] += d[*r];
s2.erase(*r); s1.erase(r);
}
else c = 0;
auto l = s1.upper_bound(i);
if (l != s1.begin()) {
--l;
d[i] += d[*l];
s2.erase(*l); s1.erase(l);
}
else c = 0;
if (c) { s1.insert(i); s2.insert(i); }
#ifdef HOME
for (int e : s1) cout << e << ' ' << d[e] << '\n';
#endif
}
}
