#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
signed main (signed argc, char **argv) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
map<int, int> mp;
set<pair<int, int>> st;
for (int i = 0, a; i < n; i++) {
cin >> a;
mp[i] = a;
st.insert({a, i});
}
int ans = 0;
mp[-1] = mp[n] = -1e16;
for (int i = 0; i < n/2+n%2; i++) {
auto f = *--st.end();
st.erase(--st.end());
ans += f.f;
auto it = mp.find(f.s);
int v = -(*it).s;
if (it != mp.begin()) {
--it;
v += (*it).s;
st.erase({(*it).s, (*it).f});
mp.erase(it);
}
it = mp.find(f.s);
if (++it != mp.end()) {
v += (*it).s;
st.erase({(*it).s, (*it).f});
mp.erase(it);
}
mp.erase(mp.find(f.s));
mp[f.s] = v;
st.insert({v, f.s});
cout << ans << "\n";
}
}
/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┗━┓ ┏━┛ + +
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the llama protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
//thanks cindy
