#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
vl w;
int main() {
ios::sync_with_stdio(0);cin.tie(0);
ll n;
cin >> n;
for(int i=0;i<n;i++) {
ll t;
cin >> t;
w.push_back(t);
}
multiset<ll,greater<ll> > bs[2],dis[2];
ll cu = 0;
for(int i=n-1;i>=0;i--) {
int nu = 1-cu;
bs[nu].insert(w[i]);
dis[nu].insert(w[i]);
ll dif = 0;
while(!dis[nu].empty() && !dis[cu].empty() && (*dis[nu].begin()+dif) <= (*dis[cu].begin())) {
auto wa = dis[nu].begin();
auto wb = dis[cu].begin();
dif += (*wa)-(*wb);
bs[nu].erase(bs[nu].find(*wa));
bs[nu].insert(*wb);
dis[nu].erase(wa);
dis[cu].erase(wb);
}
if(!dis[nu].empty()) {
ll wa = *dis[nu].begin();
bs[nu].insert(wa+dif);
dis[nu].insert(wa+dif);
bs[nu].erase(bs[nu].find(wa));
dis[nu].erase(dis[nu].find(wa));
}
cu = nu;
}
ll ru = 0;
for(auto& it: bs[cu]) {
ru += it;
cout << ru << '\n';
}
}
