#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
const int maxn = 2e5+7;
int tab[maxn];
int lewy[maxn];
int prawy[maxn];
int nr[maxn];
ll val[maxn];
ll wyn[maxn];
bool usuniete[maxn];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
priority_queue<pll> Q;
for(int i=1;i<=n;i++){
cin>>tab[i];
lewy[i] = i;
prawy[i] = i;
nr[i] = i;
val[i] = tab[i];
Q.push({val[i],i});
}
for(int i=1;i<=(n+1)/2;i++){
auto [x,ind] = Q.top();
Q.pop();
if(usuniete[ind]){
i--;
continue;
}
//cout<<ind<<" "<<x<<"\n";
wyn[i] = wyn[i-1] + val[ind];
val[ind] = -val[ind];
int s;
s = nr[lewy[ind]-1];
if(lewy[ind] == 1 || usuniete[s]){
usuniete[ind] = 1;
}
else{
val[ind] += val[s];
lewy[ind] = lewy[s];
nr[lewy[ind]] = ind;
}
usuniete[s] = 1;
s = nr[prawy[ind]+1];
if(prawy[ind] == n || usuniete[s]){
usuniete[ind] = 1;
}
else{
val[ind] += val[s];
prawy[ind] = prawy[s];
nr[prawy[ind]] = ind;
}
usuniete[s] = 1;
//cout<<ind<<" "<<lewy[ind]<<" "<<prawy[ind]<<" "<<val[ind]<<"\n";
if(!usuniete[ind]){
Q.push({val[ind],ind});
}
}
for(int i=1;i<=(n+1)/2;i++){
cout<<wyn[i]<<"\n";
}
return 0;
}
