#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const ll linf = 1e18;
set<pair<ll, ll>> a, b;
void Add(ll x, ll y) {
a.insert({x, y});
b.insert({y, x});
}
void Rem(ll x, ll y) {
a.erase({x, y});
b.erase({y, x});
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n; cin >> n;
vector<ll> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
Add(i, v[i]);
}
Add(-1, -linf); Add(n, -linf);
ll ans = 0;
for (int i = 0; i < (n + 1) / 2; i++) {
auto it = b.rbegin();
auto o = *it;
ans += o.first;
cout << ans << en;
auto itt = a.lower_bound({o.second, o.first});
auto x = *prev(itt);
auto y = *itt;
auto z = *next(itt);
Rem(x.first, x.second);
Rem(y.first, y.second);
Rem(z.first, z.second);
Add(y.first, x.second + z.second - y.second);
}
return 0;
}
