#include <bits/stdc++.h>
#define int long long int
using namespace std;
const int maxn = 2e5 + 100;
int n, a[maxn], ans = 0;
set<pair<int ,int>> s;
set<int> active;
void in(){
cin >> n;
for(int i = 0 ;i < n; i++){
cin >> a[i];
s.insert({a[i], i});
active.insert(i);
}
}
void Engine(){
while(active.size() > 0){
pair<int ,int> v = *s.rbegin();
s.erase(*s.rbegin());
ans += v.first;
cout << ans << "\n";
if(active.size() == 1){
break;
}
if(v.second == *active.begin()){
active.erase(*active.begin());
s.erase({a[*active.begin()], *active.begin()});
active.erase(*active.begin());
continue;
}
if(v.second == *active.rbegin()){
active.erase(*active.rbegin());
s.erase({a[*active.rbegin()], *active.rbegin()});
active.erase(*active.rbegin());
continue;
}
active.erase(v.second);
auto ind = lower_bound(active.begin(), active.end(), v.second);
auto nxt = ind;
auto pre = prev(ind);
active.erase(nxt), active.erase(pre);
s.erase({a[*nxt], *nxt});
s.erase({a[*pre], *pre});
a[v.second] = a[*pre] + a[*nxt] - a[v.second];
s.insert({a[v.second], v.second});
active.insert(v.second);
}
}
int32_t main(){
ios::sync_with_stdio(0) ,cout.tie(0) ,cin.tie(0);
in();
Engine();
return 0;
}
