#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> ii;
set<ii> best;
set<long long> idx;
int main(){
int n;
cin >> n;
long long arr[n];
for(int i = 0;i < n;i++){
cin >> arr[i];
best.insert(ii(arr[i],i));
idx.insert(i);
}
idx.insert(-1);
idx.insert(n+1);
long long ans = 0;
for(int k = 1;k <= (n+1)/2;k++){
set<ii>::iterator it = (--best.end());
best.erase(it);
idx.erase(it->second);
ans += it->first;
int s = it->second;
long long r = *idx.upper_bound(s);
long long l = *(--idx.lower_bound(s));
arr[s] *= -1;
if(l >= 0){
arr[s] += arr[l];
best.erase(ii(arr[l],l));
idx.erase(l);
}
if(r <= n-1){
arr[s] += arr[r];
best.erase(ii(arr[r],r));
idx.erase(r);
}
if(r <= n-1 && l >= 0){
best.insert(ii(arr[s],s));
idx.insert(s);
}
cout << ans << "\n";
}
}
