#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
const int MXN = 200005;
const ll INF = 3.9e18;
int n;
ll a[MXN], ans;
set<pil> pos;
multiset<pli> S;
void PRE() {
FOR(i, 0, n + 2) {
pos.insert(mp(i, a[i]));
S.insert(mp(a[i], i));
}
}
void miku() {
cin >> n;
FOR(i, 1, n + 1) cin >> a[i];
a[0] = -INF;
a[n + 1] = -INF;
PRE();
FOR(i, 0, n / 2 + n % 2) {
// for (auto [v, j] : pos) debug(v, j);
auto [val, p] = *S.rbegin();
ans += val;
auto it = pos.find(mp(p, val));
auto itl = prev(it), itr = next(it);
auto [l, vl] = *itl;
auto [r, vr] = *itr;
FOR($, 0, 3) {
itl = pos.erase(itl);
}
S.erase(S.find(mp(val, p)));
S.erase(S.find(mp(vl, l)));
S.erase(S.find(mp(vr, r)));
pos.insert(mp(l, vl + vr - val));
S.insert(mp(vl + vr - val, l));
cout << ans << '\n';
}
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
