#include <bits/stdc++.h>
using namespace std;
using ll = long long;
signed main() {
int n; cin >> n;
vector<ll> a(n+2, -1e18);
for(int i=1; i<=n; i++) cin >> a[i];
vector<int> L(n+2), R(n+2), vis(n+1);
for(int i=1; i<=n; i++) {
L[i] = i - 1;
R[i] = i + 1;
}
priority_queue<pair<ll, ll> > pq;
for(int i=1; i<=n; i++) pq.push({ a[i], i });
ll ans = 0;
for(int i=1; i<=(n+1)/2; i++) {
while(!pq.empty() && vis[pq.top().second]) pq.pop();
assert(!pq.empty());
auto [val, p] = pq.top(); pq.pop();
ans += val;
vis[L[p]] = vis[R[p]] = 1;
pq.push({ a[p] = a[L[p]] + a[R[p]] - a[p], p });
L[p] = L[L[p]];
R[p] = R[R[p]];
R[L[p]] = p;
L[R[p]] = p;
cout << ans << '\n';
}
}
