#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
int n,m,T,k;
void test_case() {
cin>>n;
int arr[n+1],pref[n+2],p[n+2]; pref[0]=0; p[0]=0; p[n+1]=n+1; pref[n+1]=0;
map<pii,int> mymap;
for (int i=1; i<=n; i++) {
cin>>arr[i];
if (i>1) pref[i]=pref[i-2]+arr[i];
else pref[i]=arr[i];
p[i]=i;
mymap[{i,i}]=-arr[i];
}
set<pair<int,pii>> myset;
for (int i=1; i<=n; i++) myset.insert({-arr[i],{i,i}});
int ans=0;
for (int j=1; j<=(n+1)/2; j++) {
pair<int,pii> A=*myset.begin(); myset.erase(A);
int val=-A.f,l=A.s.f,r=A.s.s;
ans+=val;
if (l-1>=0) {
int L=p[l-1],R=l-1;
myset.erase({mymap[{L,R}],{L,R}});
l=p[l-1];
}
if (r+1<=n+1) {
int L=r+1,R=p[r+1];
myset.erase({mymap[{L,R}],{L,R}});
r=p[r+1];
}
p[l]=r; p[r]=l;
int num1=pref[r]-pref[l]+arr[l];
int num2=pref[r-1]-pref[l+1]+arr[l+1];
int dif=num1-num2;
if (l==0 || r==n+1) dif=-1e18;
myset.insert({-dif,{l,r}});
mymap[{l,r}]=-dif;
// cout<<j<<" "<<l<<" "<<r<<endl;
cout<<ans<<endl;
}
}
main () {
ios :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
T=1;
while (T--) test_case();
}
