#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)2e5 + 10;
ll f[N];
int main(){
fastIO;
int n;
cin >> n;
set<int> idx;
set<pii> vals;
for(int i = 1; i <= n; i ++ ){
cin >> f[i];
idx.insert(i);
vals.insert(mp(f[i], i));
}
ll sum = 0;
int id;
bool keep;
for(int i = 0 ; i < (n + 1) / 2; i ++ ){
auto it = vals.end();
-- it;
sum += it->fi;
cout << sum << "\n";
id = it->se;
vals.erase(it);
idx.erase(id);
f[id]=-f[id];
auto ri = idx.lower_bound(id+1);
auto li = idx.lower_bound(id);
keep = true;
if(li == idx.begin()){
keep = false;
}
else{
li -- ;
f[id] += f[*li];
vals.erase(mp(f[*li], *li));
idx.erase(li);
}
if(ri == idx.end()){
keep = false;
}
else{
f[id] += f[*ri];
vals.erase(mp(f[*ri], *ri));
idx.erase(ri);
}
if(keep){
vals.insert(mp(f[id], id));
idx.insert(id);
}
}
return 0;
}
