#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, ans = 0;
cin >> n;
vector<int> a(n);
set<int> e;
set<pair<int, int>> st;
for (int i = 0; i < n; i++) {
cin >> a[i];
e.insert(i);
st.insert({a[i], i});
}
for (int it = 1; it <= (n + 1) / 2; it++) {
auto [val, id] = *st.rbegin();
ans += val;
if (e.size() > 2) {
if (id == *e.begin()) {
st.erase({a[id], id});
e.erase(id);
int lb = *e.begin();
st.erase({a[lb], lb});
e.erase(lb);
} else if (id == *e.rbegin()) {
st.erase({a[id], id});
e.erase(id);
int lb = *e.rbegin();
st.erase({a[lb], lb});
e.erase(lb);
} else {
auto it = --e.lower_bound(id);
int l = a[*it], ll = *it;
it = e.upper_bound(id);
int r = a[*it], rr = *it;
st.erase({l, ll}); e.erase(ll);
st.erase({r, rr}); e.erase(rr);
st.erase({a[id], id});
a[id] = l + r - a[id];
st.insert({a[id], id});
}
}
cout << ans << '\n';
}
}
