#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
multiset<vector<int>> st1, st2;
for(int i = 0; i < n; ++i){
st1.insert({i, a[i], 1});
st2.insert({a[i], i, 1});
}
int cnt = 0, sum = 0;
multiset<vector<int>>::iterator sv;
int dosv = 0;
while(cnt < (n + 1) / 2){
auto p2 = prev(st2.end());
if(dosv){
dosv = 0;
p2 = sv;
}
while(p2 != st2.begin() && (*p2)[2] == 0 && (*p2)[0] < 0){
--p2;
}
int nowi = (*p2)[1];
cnt += (*p2)[2], sum += (*p2)[0];
if((*p2)[2] > 0){
cout << sum << endl;
}
int dcnt = -(*p2)[2], dsum = -(*p2)[0];
auto p1 = st1.lower_bound(vector<int>{nowi, -(int)1e18, -(int)1e18});
if(p1 != st1.begin()){
auto p1p = prev(p1);
dsum += (*p1p)[1];
dcnt += (*p1p)[2];
st2.erase(st2.find(vector<int>{(*p1p)[1], (*p1p)[0], (*p1p)[2]}));
st1.erase(p1p);
}
auto p1n = next(p1);
if(p1n != st1.end()){
dsum += (*p1n)[1];
dcnt += (*p1n)[2];
st2.erase(st2.find(vector<int>{(*p1n)[1], (*p1n)[0], (*p1n)[2]}));
st1.erase(p1n);
}
st2.insert({dsum, nowi, dcnt});
st1.insert({nowi, dsum, dcnt});
if(dcnt == 0 && dsum >= 0){
dosv = 1;
sv = st2.find(vector<int>{dsum, nowi, dcnt});
}
st2.erase(p2);
st1.erase(p1);
}
return 0;
}
