#include <bits/stdc++.h>
#define int long long
int n,m,T,k;
int main() {
std::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;
std::map<std::pair<int,int>,int> mp;
for (int i=1; i<=n; i++) {
std::cin>>arr[i];
if (i>1) pref[i]=pref[i-2]+arr[i];
else pref[i]=arr[i];
p[i]=i;
mp[{i,i}]=-arr[i];
}
std::set<std::pair<int,std::pair<int,int>>> setV;
for (int i=1;i<=n;i++)setV.insert({-arr[i],{i,i}});
int ans=0;
for (int j=1;j<=(n+1)/2;j++) {
std::pair<int,std::pair<int,int>> A=*setV.begin(); setV.erase(A);
int val=-A.first,l=A.second.first,r=A.second.second;
ans+=val;
if (l-1>=0) {
int L=p[l-1],R=l-1;
setV.erase({mp[{L,R}],{L,R}});
l=p[l-1];
}
if (r+1<=n+1) {
int L=r+1,R=p[r+1];
setV.erase({mp[{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;
setV.insert({-dif,{l,r}});
mp[{l,r}]=-dif;
std::cout<<ans<<'\n';
}
}
