#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
struct Group
{
ll val;
pair<int,int> seg;
Group(){}
Group(ll a, int b, int c){ val=a;seg=mp(b,c);}
Group(ll a, pair<int,int> b){ val=a;seg=b;}
bool operator < (Group b) const { return val>b.val || val==b.val && seg<b.seg;}
};
set<Group> best;
set<pair<int,int> > ord;
set<pair<int,int> >::iterator it;
const int N=400050;
int a[N],n;
ll sum[N];
ll get(pair<int,int> p){ return sum[p.second]+(p.first>0?sum[p.first-1]:0);}
void Del(pair<int,int> p)
{
//printf("Del: (%i %i)\n",p.first,p.second);
if(p.first>=1 && p.second<=n) best.erase(Group(get(p),p));
ord.erase(p);
}
void Ins(pair<int,int> p)
{
//printf("Ins: (%i %i)\n",p.first,p.second);
if(p.first>=1 && p.second<=n) best.insert(Group(get(p),p));
if(p.first>=1 || p.second<=n) ord.insert(p);
}
void Debug()
{
set<Group>::iterator it;
for(it=best.begin();it!=best.end();it++)
{
printf("%lld:(%i %i) ",it->val,it->seg.first,it->seg.second);
}
printf("\n");
}
int main()
{
int i;
scanf("%i",&n);
for(i=1;i<=n;i++)
{
scanf("%i",&a[i]);
sum[i]=-sum[i-1]+a[i];
ord.insert(mp(i,i));
best.insert(Group(a[i],i,i));
}
for(i=n+1;i<=n*2;i++) sum[i]=-sum[i-1];
ll sol=0;int cnt=0;
while(best.size())
{
//Debug();
Group tmp=*best.begin();
//best.erase(tmp);
sol+=tmp.val;
it=ord.find(tmp.seg);
pair<int,int> dl=*it;
//printf("%i %i\n",tmp.seg.first,tmp.seg.second);
tmp.seg.first--;
tmp.seg.second++;
pair<int,int> p;
if(it!=ord.begin())
{
it--;p=*it;it++;
//printf("Left: (%i %i)\n",p.first,p.second);
if(p.second==tmp.seg.first)
{
Del(p);
//best.erase(Group(get(p),p));
//ord.erase(p);
tmp.seg.first=p.first;
}
}
it++;
if(it!=ord.end())
{
p=*it;
//printf("Right: (%i %i)\n",p.first,p.second);
if(p.first==tmp.seg.second)
{
Del(p);
//best.erase(Group(get(p),p));
//ord.erase(p);
tmp.seg.second=p.second;
}
}
it--;
Del(dl);
//ord.erase(*it);
Ins(tmp.seg);
//if(tmp.seg.first>=1 || tmp.seg.second<=n)
//{
// if(tmp.seg.first>=1 && tmp.seg.second<=n) best.insert(Group(get(tmp.seg),tmp.seg));
// ord.insert(tmp.seg);
//}
cnt++;//printf("%i ",cnt);
printf("%lld\n",sol);
//if(cnt==(n+1)/2) break;
}
return 0;
}
