#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL inf = 1E18;
int main(){
cin.tie(0)->sync_with_stdio(0);
int N;
cin >> N;
vector<LL> A(N + 2);
for(int i = 1;i <= N;i ++){
cin >> A[i];
}
A[0] = -inf;
A[N + 1] = -inf;
LL ans = 0;
set<pair<LL , int>> S;
for(int i = 1;i <= N;i ++){
S.insert({A[i] , i});
}
set<int> ids;
for(int i = 0;i <= N + 1;i ++){
ids.insert(i);
}
for(int i = 1;i <= (N + 1) / 2;i ++){
auto [best , j] = *--S.end();
S.erase(--S.end());
ans += best;
int prv = *--ids.lower_bound(j);
int nxt = *ids.upper_bound(j);
if(prv > 0){
ids.erase(prv);
S.erase({A[prv] , prv});
}
if(nxt <= N){
ids.erase(nxt);
S.erase({A[nxt] , nxt});
}
cout << ans << '\n';
A[j] = A[prv] + A[nxt] - A[j];
S.insert({A[j] , j});
}
}
