#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(make_pair(a[i], i));
active.insert(i);
}
}
void Engine(){
while(active.size() > 0){
pair<int ,int> v = *s.rbegin();
s.erase(v);
ans += v.first;
cout << ans << "\n";
if(active.size() == 1){
break;
}
if(v.second == (*active.begin())){
active.erase(*active.begin());
s.erase(make_pair(a[*active.begin()], *active.begin()));
active.erase(*active.begin());
continue;
}
if(v.second == (*active.rbegin())){
active.erase(*active.rbegin());
s.erase(make_pair(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(make_pair(a[*nxt], *nxt));
s.erase(make_pair(a[*pre], *pre));
a[v.second] = a[*pre] + a[*nxt] - a[v.second];
s.insert(make_pair(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;
}
