#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const long long INF=-1e18;
set< pair<long long,int> > st;
set<int> pos;
long long A[MAXN];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>A[i];
st.insert({A[i],i}),pos.insert(i);
}
pos.insert(0),pos.insert(n+1),A[0]=A[n+1]=INF;
long long ans=0;
for(int i=1;i<=(n+1)/2;i++)
{
int p;
pair<long long,int> val=*prev(st.end());
ans+=val.first,p=val.second,st.erase(val);
auto res=pos.find(p);
int l=*(prev(res)),r=*(next(res));
if(l>=1) pos.erase(l),st.erase({A[l],l});
if(r<=n) pos.erase(r),st.erase({A[r],r});
st.insert({A[p]=-A[p]+A[l]+A[r],p});
cout<<ans<<"\n";
}
}
