#include <bits/stdc++.h>
using namespace std;
const int N = 200'000 + 10;
int n;
long long a[N];
bool isDel[N];
int nxt[N], pre[N];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
iota(nxt + 1, nxt + n + 1, 2);
iota(pre + 1, pre + n + 1, 0);
priority_queue<pair<long long, int>> q;
for (int i = 1; i <= n; ++i) q.push({a[i], i});
a[0] = a[n + 1] = -1'000'000'000'000'000'000;
long long answer = 0;
for (int i = 1; i <= (n + 1) / 2; ++i) {
while (q.size() && isDel[q.top().second]) q.pop();
auto [value, id] = q.top(); q.pop();
answer += value;
a[id] = -a[id] + a[pre[id]] + a[nxt[id]];
q.push({a[id], id});
isDel[pre[id]] = isDel[nxt[id]] = true;
nxt[pre[pre[id]]] = id;
pre[nxt[nxt[id]]] = id;
pre[id] = pre[pre[id]];
nxt[id] = nxt[nxt[id]];
cout << answer << "\n";
}
}
