#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll
mt19937 rnd(239);
struct DSU {
vector<int> p, l, r;
DSU(int n) {
p.resize(n + 1);
l.resize(n + 1);
r.resize(n + 1);
iota(all(p), 0);
iota(all(l), 0);
iota(all(r), 0);
}
int find(int v) {
return p[v] == v ? v : p[v] = find(p[v]);
}
void merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) {
return;
}
if (rnd() & 1) {
swap(a, b);
}
p[b] = a;
l[a] = min(l[a], l[b]);
r[a] = max(r[a], r[b]);
}
};
struct ST {
vector<int> t;
void init(int n) {
t.resize(4 * n + 10, -1);
}
void push(int v) {
if (t[v] != -1) {
t[2 * v] = t[v];
t[2 * v + 1] = t[v];
t[v] = -1;
return;
}
}
void update(int v, int l, int r, int a, int b, int vl) {
if (l > b || r < a) {
return;
}
if (l >= a && r <= b) {
t[v] = vl;
return;
}
push(v);
int mid = (l + r) / 2;
update(2 * v, l, mid, a, b, vl);
update(2 * v + 1, mid + 1, r, a, b, vl);
}
int get(int v, int l, int r, int need) {
if (l == r) {
return t[v];
}
push(v);
int mid = (l + r) / 2;
if (need <= mid) {
return get(2 * v, l, mid, need);
}
else {
return get(2 * v + 1, mid + 1, r, need);
}
}
/*void init(int n) {
t.resize(n + 1);
}
void update(int v, int l, int r, int a, int b, int vl) {
for (int i = a; i <= b; i++) {
t[i] = vl;
}
}
int get(int v, int l, int r, int need) {
return t[need];
}*/
};
ST tree1, tree2;
const int N = 2e5 + 10;
int a[N], pref[N];
inline int get_sum(int l, int r) {
int rez = pref[r] - pref[l - 1];
if (l % 2 == 0) {
rez *= -1;
}
return rez;
}
int n;
inline int check(int x) {
if (x & 1) {
return tree1.get(1, 1, n, x);
}
else {
return tree2.get(1, 1, n, x);
}
}
set<int> unmerged[2];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1];
if (i & 1) {
pref[i] += a[i];
}
else {
pref[i] -= a[i];
}
}
for (int i = 1; i + 2 <= n; i++) {
unmerged[i % 2].insert(i);
}
tree1.init(n);
tree2.init(n);
DSU kek(n);
tree1.update(1, 1, n, 1, n, 0);
tree2.update(1, 1, n, 1, n, 0);
set<pair<int, int>> can;
for (int i = 1; i <= n; i++) {
can.insert({a[i], i});
}
set<pair<int, pair<int, int>>> can_flip;
int all = 0;
for (int i = 1; i <= (n + 1) / 2; i++) {
pair<int, int> mx = {-1e18, 0};
if (!can.empty()) {
mx = *(--can.end());
}
pair<int, pair<int, int>> mx2 = {-1e18, {0, 0}};
if (!can_flip.empty()) {
mx2 = *(--can_flip.end());
}
if (mx.F > mx2.F) {
all += mx.F;
can.erase(--can.end());
//cout << 1 << ' ' << mx.S << '\n';
if (mx.S > 1 && can.find({a[mx.S - 1], mx.S - 1}) != can.end()) {
can.erase({a[mx.S - 1], mx.S - 1});
}
if (mx.S < n && can.find({a[mx.S + 1], mx.S + 1}) != can.end()) {
can.erase({a[mx.S + 1], mx.S + 1});
}
if (mx.S & 1) {
tree1.update(1, 1, n, mx.S, mx.S, 1);
}
else {
tree2.update(1, 1, n, mx.S, mx.S, 1);
}
if (mx.S > 2 && check(mx.S - 2)) {
int comp = kek.find(mx.S - 2);
if (kek.l[comp] > 1 && kek.r[comp] < n) {
can_flip.erase(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
}
unmerged[mx.S % 2].erase(mx.S - 2);
kek.merge(mx.S, mx.S - 2);
}
if (mx.S + 2 <= n && check(mx.S + 2)) {
int comp = kek.find(mx.S + 2);
if (kek.l[comp] > 1 && kek.r[comp] < n) {
can_flip.erase(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
}
unmerged[mx.S % 2].erase(mx.S);
kek.merge(mx.S, mx.S + 2);
}
int comp = kek.find(mx.S);
if (kek.l[comp] > 1 && kek.r[comp] < n) {
can_flip.insert(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
}
}
else {
//cout << i << ' ' << 2 << '\n';
all += mx2.F;
int L = mx2.S.F, R = mx2.S.S;
//cout << L << ' ' << R << '\n';
if (L > 2 && can.find({a[L - 2], L - 2}) != can.end()) {
can.erase({a[L - 2], L - 2});
}
if (R + 2 <= n && can.find({a[R + 2], R + 2}) != can.end()) {
can.erase({a[R + 2], R + 2});
}
if (L & 1) {
tree1.update(1, 1, n, L, R, 0);
tree2.update(1, 1, n, L - 1, R + 1, 1);
}
else {
tree2.update(1, 1, n, L, R, 0);
tree1.update(1, 1, n, L - 1, R + 1, 1);
}
can_flip.erase(--can_flip.end());
L--, R++;
for (;;) {
auto it = unmerged[L % 2].lower_bound(L);
if (it == unmerged[L % 2].end() || *it > R - 2) {
break;
}
kek.merge(*it, *it + 2);
unmerged[L % 2].erase(it);
//cout << "C " << *it << '\n';
}
if (L > 2 && check(L - 2)) {
int comp = kek.find(L - 2);
if (kek.l[comp] > 1 && kek.r[comp] < n) {
can_flip.erase(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
}
unmerged[L % 2].erase(L - 2);
kek.merge(L, L - 2);
}
if (R + 2 <= n && check(R + 2)) {
int comp = kek.find(R + 2);
if (kek.l[comp] > 1 && kek.r[comp] < n) {
can_flip.erase(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
}
unmerged[R % 2].erase(R);
kek.merge(R, R + 2);
}
int comp = kek.find(L);
if (kek.l[comp] > 1 && kek.r[comp] < n) {
can_flip.insert(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
}
}
cout << all << '\n';
/*for (int i = 1; i <= n; i++) {
cout << check(i) << ' ';
}
cout << '\n';*/
}
}
