#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = (int) 2e5 + 7;
const ll INF = (ll) 1e18;
int n, sol[N];
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("input", "r", stdin);
cin >> n;
set<pair<int, int>> s, revs;
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
s.insert({-x, i});
revs.insert({i, -x});
}
s.insert({INF, 0});
revs.insert({0, INF});
s.insert({INF, n + 1});
revs.insert({n + 1, INF});
sol[0] = 0;
for (int i = 1; i <= (n + 1) / 2; i++) {
pair<int, int> now = *s.begin();
sol[i] = sol[i - 1] - now.first;
auto it = revs.lower_bound({now.second, -INF});
it--;
pair<int, int> x = *it;
s.erase(s.find({x.second, x.first}));
revs.erase(it++);
pair<int, int> y = *it;
s.erase(s.find({y.second, y.first}));
revs.erase(it++);
pair<int, int> z = *it;
s.erase(s.find({z.second, z.first}));
revs.erase(it++);
revs.insert({y.first, x.second + z.second - y.second});
s.insert({x.second + z.second - y.second, y.first});
}
for (int i = 1; i <= (n + 1) / 2; i++) {
cout << sol[i] << "\n";
}
return 0;
}
