#include <bits/stdc++.h>
using namespace std;
#define int long long
set<pair<int,int>>S;
const int N=1e6+3, MAXN=(1<<20), INF=1e15;
int a[N], pref[N];
pair<int,int> D[2*MAXN+3];
int calc_kon(int ind)
{
int kon=ind;
auto it=S.lower_bound({ind, -1});
if(it!=S.end()&&(*it).first<=ind+2)
{
auto x=*it;
if(x.first==ind+1)
{
S.erase(it);
x.first++, x.second++;
kon=x.second;
it=S.lower_bound({ind, -1});
if(it!=S.end()&&(*it).first<=kon+2)
{
kon=(*it).second;
S.erase(it);
}
}
else
{
S.erase(it);
kon=x.second;
}
}
return kon;
}
int calc_pocz(int ind)
{
int pocz=ind;
auto it=S.lower_bound({ind, -1});
if(it==S.begin())return pocz;
it--;
if((*it).second>=ind-2)
{
auto x=*it;
if(x.second==ind-1)
{
S.erase(it);
x.first--, x.second--;
pocz=x.first;
auto it=S.lower_bound({ind, -1});
if(it==S.begin())return pocz;
it--;
if((*it).second>=pocz-2)
{
pocz=(*it).first;
S.erase(it);
}
}
else
{
S.erase(it);
pocz=x.first;
}
}
return pocz;
}
bool ok(int ind)
{
auto it=S.lower_bound({ind+1, -1});
if(it!=S.begin())
{
it--;
if((*it).first<=ind&&(*it).second>=ind)return false;
}
return true;
}
void update(int x, int val)
{
x+=MAXN;
D[x].first=val;
x/=2;
while(x>0)
{
D[x]=max(D[2*x], D[2*x+1]);
x/=2;
}
}
int suma(int pocz, int kon)
{
int s=pref[kon];
if(pocz>=2)s-=pref[pocz-2];
return s;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
}
a[0]=-INF, a[n+1]=-INF;
for(int i=0; i<=n+1; i++)
{
pref[i]=a[i];
if(i>=2)pref[i]+=pref[i-2];
}
for(int i=0; i<=2*MAXN; i++)D[i]= {-INF, i};
for(int i=1; i<=n; i++)D[i+MAXN]= {a[i], i};
for(int i=MAXN-1; i>=1; i--)D[i]=max(D[2*i], D[2*i+1]);
int res=0;
for(int i=1; i<=(n+1)/2; i++)
{
while(!ok(D[1].second))
{
update(D[1].second, -INF);
}
res+=D[1].first;
cout<<res<<"\n";
int ind=D[1].second;
int pocz=calc_pocz(ind), kon=calc_kon(ind);
S.insert({pocz, kon});
if(pocz-1>0)update(pocz-1,suma(pocz-1, kon+1)-suma(pocz, kon));
if(kon+1<=n)update(kon+1,suma(pocz-1, kon+1)-suma(pocz, kon));
}
return 0;
}
