// ~ Be Name Khoda ~
#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
set <pair<ll, int>> seg, av;
ll a[maxn5], sum[maxn5], have[maxn5];
int pre[maxn5], l[maxn5], r[maxn5], nxt[maxn5];
inline int merge(int v){
int u = nxt[v];
int z = nxt[u];
nxt[v] = z;
if(z != -1)
pre[z] = v;
av.erase({-(sum[u] - 2 * have[u]), u});
av.erase({-(sum[v] - 2 * have[v]), v});
sum[v] += sum[u];
have[v] += have[u];
l[v] = min(l[v], l[u]);
r[v] = max(r[v], r[u]);
return v;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
for(int i = 0; i < n; i++){
cin >> sum[i];
av.insert({-sum[i], i});
l[i] = r[i] = i;
pre[i] = i - 1;
nxt[i] = i + 1;
}
nxt[n - 1] = -1;
ll cur = 0;
for(int i = 1; i <= (n + 1) / 2; i++){
int v = av.begin()->se;
av.erase(av.begin());
cur += sum[v] - 2 * have[v];
have[v] = sum[v] - have[v];
if(nxt[v] != -1)
v = merge(v);
if(pre[v] != -1)
v = merge(pre[v]);
if((r[v] - l[v] + 1) & 1)
av.insert({-(sum[v] - 2 * have[v]), v});
cout << cur << '\n';
}
}
/*
5
3 5 1 7 6
*/
