#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=202000;
const int mxM=104;
const int mxK=1000000;
const ll MOD=1000000007;
const ll INF=100000000000001;
typedef struct rng{
int l, r;
ll val;
}rng;
typedef struct cmp1{
bool operator()(rng a, rng b)
{
return a.val<b.val;
}
}cmp1;
int N;
ll A[mxN];
priority_queue <rng, vector<rng>, cmp1> pq;
int par[mxN];
rng uf[mxN];
ll ans;
int L, R;
int findpar(int a)
{
return par[a]==a ? a : (par[a]=findpar(par[a]));
}
int main()
{
gibon
cin >> N;
for(int i=1;i<=N;i++) cin >> A[i];
L=0, R=N+1;
for(int i=1;i<=N;i++)
{
par[i]=i;
uf[i].l=uf[i].r=i, uf[i].val=A[i];
pq.push(uf[i]);
}
for(int i=1;i<=(N+1)/2;i++)
{
while(true)
{
rng now=pq.top();
pq.pop();
int ncur=findpar(now.l);
if(uf[ncur].l!=now.l || uf[ncur].r!=now.r || uf[ncur].l<=L || uf[ncur].r>=R) continue;
ans+=now.val;
uf[ncur].val*=-1;
cout << ans << '\n';
if(i==(N+1)/2) break;
if(uf[ncur].l==L+1)
{
L=uf[findpar(uf[ncur].r+1)].r;
break;
}
if(uf[ncur].r==R-1)
{
R=uf[findpar(uf[ncur].l-1)].l;
break;
}
int lc=findpar(uf[ncur].l-1);
par[lc]=ncur;
uf[ncur].val+=uf[lc].val;
uf[ncur].l=uf[lc].l;
int rc=findpar(uf[ncur].r+1);
par[rc]=ncur;
uf[ncur].val+=uf[rc].val;
uf[ncur].r=uf[rc].r;
pq.push(uf[ncur]);
break;
}
}
}
