#include <bits/stdc++.h>
using namespace std;
int a[200005];
struct state{
int u, v;
long long nw, ow;
state(int x, int y, long long z, long long t) : u(x), v(y), nw(z), ow(t) {}
friend bool operator<(const state& x, const state& y){
if(x.nw - x.ow != y.nw - y.ow) return x.nw - x.ow < y.nw - y.ow;
return make_pair(x.u, x.v) < make_pair(y.u, y.v);
}
};
set<pair<int,int> > ranges; // picked ranges
set<pair<int,int> > options; // potential options (sorted by pair)
set<state> states; // potential options
set<pair<int,int> >::iterator isCovered(int x){
// checks whether x is covered?
auto it = ranges.upper_bound(make_pair(x, 1000000));
if(it == ranges.begin()) return ranges.end();
it--;
return it->second >= x ? it : ranges.end();
}
set<pair<int,int> >::iterator isOptionsCovered(int x){
// checks whether x is covered?
auto it = options.upper_bound(make_pair(x, 1000000));
if(it == options.begin()) return options.end();
it--;
return it->second >= x ? it : options.end();
}
long long qs[200005];
long long qsx[200005];
inline long long getSum(int idx){
return idx > 0 ? qsx[idx] : 0ll;
}
int main(){
int n;
scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%d",a+i);
states.emplace(i,i,a[i],0);
options.emplace(i,i);
qsx[i] = (i-2 > 0 ? qsx[i-2] : 0ll) + a[i];
qs[i] = qs[i-1] + a[i];
}
long long ans = 0ll;
for(int turn = 1; turn <= (n+1)/2; turn++){
auto cur = *states.rbegin(); // maximum potential weight
ans += cur.nw - cur.ow;
states.erase(cur);
options.erase(make_pair(cur.u, cur.v));
if(ranges.count(make_pair(cur.u+1, cur.v-1)))
ranges.erase(make_pair(cur.u+1, cur.v-1));
// left-joinable and right-joinable?
auto lchk = cur.u > 1 ? isCovered(cur.u - 2) : ranges.end();
auto rchk = cur.v < n ? isCovered(cur.v + 2) : ranges.end();
int targetL = lchk == ranges.end() ? cur.u : lchk->first;
int targetR = rchk == ranges.end() ? cur.v : rchk->second;
if(lchk != ranges.end()){
ranges.erase(lchk);
}
auto p = isOptionsCovered(cur.u-1);
// find the props of the state
if(p != options.end()){
long long nw = getSum(p->second) - getSum(p->first - 2);
long long ow = qs[p->second] - qs[p->first-1] - nw;
state ex(p->first, p->second, nw, ow);
states.erase(ex);
options.erase(p);
}
if(rchk != ranges.end()){
ranges.erase(rchk);
}
p = isOptionsCovered(cur.v+1);
if(p != options.end()){
// find the props of the state
long long nw = getSum(p->second) - getSum(p->first - 2);
long long ow = qs[p->second] - qs[p->first-1] - nw;
state ex(p->first, p->second, nw, ow);
states.erase(ex);
options.erase(p);
}
ranges.emplace(targetL, targetR);
if(targetL-1 >= 1 && targetR+1 <= n){
options.emplace(targetL-1, targetR+1);
long long cow = getSum(targetR) - getSum(targetL-2);
states.emplace(targetL-1, targetR+1, qs[targetR+1] - qs[targetL-2] - cow, cow);
}
printf("%lld\n", ans);
}
//printf("RANGES\n");
for(auto r : ranges){
//printf("%d %d\n", r.first, r.second);
}
//printf("OPTIONS\n");
for(auto r : options){
//printf("%d %d\n", r.first, r.second);
}
//printf("STATES\n");
for(auto r : states){
//printf("%d %d\n", r.u, r.v);
}
//printf("===\n");
return 0;
}
