#include <bits/stdc++.h>
#define f first
#define s second
#define sz(x) (int)x.size()
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define nl '\n'
#define ioi exit(0);
using namespace std;
typedef long long ll;
const int N = (int)2e5 + 7;
int n;
int a[N];
pair <ll, ll> rev(pair <ll, ll> x) {
return {x.s, x.f};
}
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef IOI
freopen ("in.txt", "r", stdin);
freopen ("A.out", "w", stdout);
#endif
cin >> n;
set < pair <ll, ll > > val, ind;
rep(i, 1, n) {
cin >> a[i];
val.insert({a[i], i});
ind.insert({i, a[i]});
}
ll ans = 0;
rep(j, 1, (n + 1) / 2) {
pair <ll, ll> ai = *val.rbegin();
val.erase(--val.end());
ind.erase(rev(ai));
ans += ai.f;
ll del = -ai.f;
bool add = 1;
{
auto it = ind.upper_bound(rev(ai));
if (it != ind.end()) {
del += it -> s;
ind.erase(it);
val.erase(rev(*it));
}
else add = 0;
}
{
auto it = ind.lower_bound(rev(ai));
if (it != ind.begin()) {
--it;
del += it -> s;
ind.erase(it);
val.erase(rev(*it));
}
else add = 0;
}
if (add) {
val.insert({del, ai.s});
ind.insert({ai.s, del});
}
cout << ans << endl;
}
ioi
}
