#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define f(i, a, b) for(int i = a; i <= b; i++)
const ll ars = 2e5 + 5;
int n;
ll a[ars];
int L[ars], R[ars];
priority_queue<pll> q;
ll ans = 0;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
f(i,1,n){
cin >> a[i];
L[i] = i-1;
R[i] = i+1;
q.push({a[i], i});
}
int T = (n + 1) / 2;
for(int t = 1; t <= T; t++){
ll val; int i;
while(true){
tie(val, i) = q.top(); q.pop();
if(val == a[i]) break;
}
ans += val;
cout << ans << '\n';
int l = L[i], r = R[i];
int nl = (l >= 1 ? L[l] : 0);
int nr = (r <= n ? R[r] : n+1);
if(l >= 1 && r <= n){
a[i] = a[l] + a[r] - a[i];
q.push({a[i], i});
}
// cập nhật linked list
if(nl >= 1) R[nl] = i;
if(nr <= n) L[nr] = i;
L[i] = nl;
R[i] = nr;
}
}
