#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> a(n + 2, -1e18), l(n + 2), r(n + 2), del(n + 2);
priority_queue<pair<int, int>> pq;
for(int i = 1; i <= n; i++){
cin >> a[i];
pq.push({a[i], i});
}
for(int i = 0; i <= n + 1; i++) l[i] = i - 1, r[i] = i + 1;
r[n + 1] = n + 1, l[0] = 0;
int ans = 0;
for(int i = 1; i <= (n + 1) / 2; i++){
while(pq.size() && del[pq.top().second]) pq.pop();
auto [val, pos] = pq.top();
pq.pop();
ans += val;
cout << ans << "\n";
int ll = l[pos], rr = r[pos];
a[pos] = a[ll] + a[rr] - a[pos];
pq.push({a[pos], pos});
del[ll] = del[rr] = 1;
l[pos] = l[ll];
r[pos] = r[rr];
r[l[pos]] = l[r[pos]] = pos;
}
}
