#include <bits/stdc++.h>
#include <queue>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
os << "{";
int g = o.size();
for (auto i : o) os << i << ((--g) == 0 ? "" : ", ");
os << "}";
return os;
}
void _print() {
cerr << "\n";
}
template<typename T, typename ...V>
void _print(T t, V... v) {
cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}
#ifdef LOCAL
#define dbg(x...) cerr <<__func__ << ":" <<__LINE__ << " " << #x << " = "; _print(x);
#else
#define dbg(x...)
#endif
/*
consider how the solution changes when you add a new candy
case 1: a new candy is taken and the previous candy dont move
case 2: a new candy is taken and previous candy need to be shifted
consider the current taken candy
...X...
say we try to take an adjacent candy
...XO..
this means that the X needs to move somewhere
say the X moves here
.X..O..
this is bad, however, since
.O.X...
would be strictly better
hence, whenver you move a piece of candy, a consecutive "sequence" of candy get shuffled
make a pq of ranges
a valid range is an odd length range of alternating 0's and 1's, with two 0's on either side
*/
struct DSU {
vt<int> e, l, r;
void init(int n) {
e = l = vt<int>(n, -1);
iota(all(l), 0);
r = l;
}
int find(int x) {
return e[x] < 0 ? x : e[x] = find(e[x]);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
int nl = min(l[x], l[y]);
int nr = max(r[x], r[y]);
if (e[x] < e[y]) swap(x, y);
e[y] += e[x];
e[x] = y;
l[y] = nl;
r[y] = nr;
}
};
int n;
ll arr[200005], sfx[200005];
main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
F0R (i, n) cin >> arr[i];
F0R (i, n) sfx[i] = arr[i] * (i % 2 == 0 ? 1 : -1);
ROF (i, 0, n) sfx[i] += sfx[i + 1];
DSU dsu;
dsu.init(n);
using t3 = tuple<ll, ll, ll>;
priority_queue<t3> pq;
F0R (i, n) {
pq.push({arr[i], i, i});
}
vt<bool> used(n);
auto good = [&] (t3 x) {
auto [c, l, r] = x;
dbg(c, l, r);
return !used[l] && !used[r] && (l == 0 || !used[l - 1]) && (r == n - 1 || !used[r + 1]);
};
ll tot = 0;
FOR (_, 1, (n + 3) / 2) {
t3 cur = pq.top();
while (!good(cur)) pq.pop(), assert(pq.size()), cur = pq.top();
pq.pop();
auto [v, l, r] = cur;
tot += v;
used[l] = used[r] = 1;
if (l) dsu.unite(l, l - 1);
if (r + 1 < n) dsu.unite(r, r + 1);
int x = dsu.find(l);
int nl = dsu.l[x];
int nr = dsu.r[x];
pq.push({(sfx[nl] - sfx[nr + 1]) * (nl % 2 == 0 ? 1 : -1), nl, nr});
cout << tot << endl;
dbg(tot);
dbg(used);
dbg(l, r, nl, nr);
}
}
