#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
cin>>n;
vector<int> t(n+2);
set<int> unused;
vector<ll> cost(n+2);
set<pair<ll, int>> cost_lst;
for(int i=1;i<=n;++i) {
cin>>t[i];
unused.insert(i);
cost[i]=t[i];
cost_lst.insert({cost[i], i});
}
cost[0]=-(1LL<<60);
cost[n+1]=-(1LL<<60);
unused.insert(0);
unused.insert(n+1);
ll ans=0;
for(int j=0;j<(n+1)/2;++j) {
auto best=(--cost_lst.end())->second;
auto best_cost=(--cost_lst.end())->first;
ans+=best_cost;
unused.erase(best);
cost_lst.erase({best_cost, best});
cost[best]=-cost[best];
auto it=unused.lower_bound(best);
if(it!=unused.end()) {
cost[best]+=cost[*it];
cost_lst.erase({cost[*it], *it});
unused.erase(it);
}
it=unused.lower_bound(best);
if(it!=unused.begin()) {
it--;
cost[best]+=cost[*it];
cost_lst.erase({cost[*it], *it});
unused.erase(it);
}
unused.insert(best);
cost_lst.insert({cost[best], best});
cout<<ans<<"\n";
}
return 0;
}
