#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1;
const ll oo = 1e18;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
list<ll> lst;
struct el {
list<ll>::iterator it;
bool operator<(const el& o) const {
if(*it==*o.it) {
return it._M_node<o.it._M_node;
}
return *it < *o.it;
}
};
multiset<el> pq;
for(int i=0;i<n;++i) {
int a; cin >> a;
lst.push_back(a);
pq.insert({prev(lst.end())});
}
lst.push_back(-oo);
lst.push_front(-oo);
ll ans=0;
for(int i=1;i<=(n+1)/2;++i) {
auto e = *prev(pq.end());
pq.erase(prev(pq.end()));
ll v = *e.it;
ans+=v;
auto lit = prev(e.it);
auto rit = next(e.it);
pq.erase({lit});
pq.erase({rit});
lst.erase(e.it);
ll nv = *lit + *rit - v;
lst.erase(rit);
*lit=nv;
pq.insert({lit});
cout << ans << '\n';
}
}
