# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3;
int n, a[N];
long long ans;
set < pair<long long, long long> > val, ind;
int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
val.insert( {a[i], i} );
ind.insert( {i, a[i]} );
}
val.insert({-1e18, -1}), ind.insert({-1, -1e18});
val.insert({-1e18, n + 1}), ind.insert({n + 1, -1e18});
for(int i = 1; i <= (n + 1) / 2; i ++){
auto it = -- val.end();
ans += it->first;
auto ps = ind.find({it->second, it->first});
auto x = *prev(ps);
auto y = *ps;
auto z = *next(ps);
for(auto it : {x, y, z}){
ind.erase(it);
val.erase({it.second, it.first});
}
ind.insert({y.first, x.second + z.second - y.second});
val.insert({x.second + z.second - y.second, y.first});
cout << ans << endl;
}
}
