#include <bits/extc++.h>
#include <immintrin.h>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define ll long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) [](decltype(x) _x) {cerr << #x << " = " << _x << endl; return _x;}(x)
using pii = pair<int, int>;
// const int inf = 1 << 30;
const ll inf = 1ll << 60;
const int MOD = 1e9 + 7;
#if __cplusplus >= 201703L
template <class T, class _ = decltype(begin(declval<T>()))>
enable_if_t<!is_same_v<T, string>, ostream&> operator<<(ostream& out, T a);
template <class T, class U>
ostream& operator<<(ostream& out, pair<T, U> p) {
return out << "(" << p.f << ", " << p.s << ")";
}
template <class T, class _>
enable_if_t<!is_same_v<T, string>, ostream&> operator<<(ostream& out, T a) {
string dlm = "";
out << "{";
for(auto i : a) {
out << dlm << i;
dlm = ", ";
}
return out << "}";
}
#endif
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
vector<int> a(n + 2);
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
struct rinfo {
int l, r; // inc inc
int csum, nsum;
};
map<int, rinfo> rs; // l -> rinfo
set<pii> rv; // (v, l)
set<pii> unused; // (v, i)
for(int i = 1; i <= n; i++) {
unused.insert({a[i], i});
}
int cur = 0;
for(int j = 1; j <= (n + 1) / 2; j++) {
int mu = -inf, mr = -inf;
if(unused.size()) mu = unused.rbegin()->f;
if(rv.size()) mr = rv.rbegin()->f;
assert(max(mu, mr) > -inf);
int touched;
if(mu > mr) {
int i = unused.rbegin()->s;
rs[i - 1] = {i - 1, i + 1, a[i], a[i - 1] + a[i + 1]};
rv.insert({a[i - 1] + a[i + 1] - a[i], i - 1});
unused.erase({a[i - 1], i - 1});
unused.erase({a[i + 1], i + 1});
unused.erase(prev(unused.end()));
touched = i - 1;
cur += a[i];
} else {
int l = rv.rbegin()->s;
auto info = rs[l];
rs.erase(l);
rv.erase({info.nsum - info.csum, l});
info.l--;
info.r++;
cur -= info.csum;
swap(info.csum, info.nsum);
info.nsum += a[info.l] + a[info.r];
unused.erase({a[info.l], info.l});
unused.erase({a[info.r], info.r});
cur += info.csum;
rs[l - 1] = info;
rv.insert({info.nsum - info.csum, l - 1});
touched = l - 1;
}
auto it = rs.find(touched);
assert(it != rs.end());
if(next(it) != rs.end()) {
auto nxt = next(it);
if(it->s.r == nxt->s.l) {
rinfo m;
m.l = it->s.l;
m.r = nxt->s.r;
m.csum = it->s.csum + nxt->s.csum;
m.nsum = it->s.nsum + nxt->s.nsum - a[it->s.r];
rv.erase({it->s.nsum - it->s.csum, it->s.l});
rs.erase(it);
rv.erase({nxt->s.nsum - nxt->s.csum, nxt->s.l});
rs.erase(nxt);
rs[m.l] = m;
rv.insert({m.nsum - m.csum, m.l});
}
}
it = rs.find(touched);
if(it != rs.begin()) {
auto prv = prev(it);
if(prv->s.r == it->s.l) {
rinfo m;
m.l = prv->s.l;
m.r = it->s.l;
m.csum = prv->s.csum + it->s.csum;
m.nsum = prv->s.nsum + it->s.nsum - a[prv->s.r];
rv.erase({prv->s.nsum - prv->s.csum, prv->s.l});
rs.erase(prv);
rv.erase({it->s.nsum - it->s.csum, it->s.l});
rs.erase(it);
rs[m.l] = m;
rv.insert({m.nsum - m.csum, m.l});
}
}
cout << cur << endl;
}
}
