#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
int n;
int arr[200023];
ll pref[200023][2];
int per[200023];
int p=1;
ll ans=0;
multiset<int>locs;
set<pair<int,int>>ara;
set<pair<ll,pair<int,int>>,greater<pair<ll,pair<int,int>>>>st;
signed main(){
ios_base::sync_with_stdio(23^23);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
pref[i][0]=pref[i-1][0]+arr[i];
pref[i][1]=arr[i];
if(i>1)pref[i][1]+=pref[i-2][1];
per[i]=i;
}
sort(per+1,per+n+1,[&](const int &x,const int &y){
return arr[x]>arr[y];
});
while(st.size()||p<=n){
if(p<=n)if(ara.size()){
auto itr=ara.upper_bound({per[p]+1,-1});
if(itr!=ara.end()){
if(itr->fr==per[p]+1){
p++;
continue;
}
}
if(itr!=ara.begin()){
itr--;
if(itr->sc>=per[p]-1){
p++;
continue;
}
}
}
if(st.size()){
if(!ara.count(st.begin()->sc)){
st.erase(st.begin());
continue;
}
}
ll c;
int l,r;
if(!st.size()||(p<=n&&arr[per[p]]>=st.begin()->fr)){
c=arr[per[p]];
l=per[p]+1;
r=per[p]-1;
p++;
}
else{
c=st.begin()->fr;
l=st.begin()->sc.fr;
r=st.begin()->sc.sc;
st.erase(st.begin());
locs.erase(locs.find(l));
locs.erase(locs.find(r));
ara.erase({l,r});
}
ans+=c;
cout<<ans<<endl;
l--;r++;
auto itr=locs.upper_bound(r);
if(itr!=locs.end()){
if((*itr)==r+2){
int a=*itr;
int b=*(++itr);
locs.erase(locs.find(a));
locs.erase(locs.find(b));
ara.erase({a,b});
r=b;
}
}
itr=locs.lower_bound(l);
if(itr!=locs.begin()){
itr--;
if((*itr)+2==l){
int b=*itr;
int a=*(--itr);
locs.erase(locs.find(a));
locs.erase(locs.find(b));
ara.erase({a,b});
l=a;
}
}
locs.insert(l);
locs.insert(r);
ara.insert({l,r});
if(l==1||r==n)continue;
st.insert({pref[r+1][1]-pref[l-1][1]+arr[l-1]-(pref[r][1]-pref[l][1]+arr[l]),{l,r}});
}
}
