#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int32_t main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
vector<ll> arr(N), L(N, -1), R(N, -1);
set<array<ll, 2>> s;
for (int i = 0;i < N;i ++) {
cin >> arr[i];
s.insert({arr[i], i});
if (i - 1 >= 0) L[i] = i - 1;
if (i + 1 < N) R[i] = i + 1;
}
ll sum = 0;
for (int i = 1;i <= (N + 1) / 2;i ++) {
auto it = *s.rbegin();
s.erase(-- s.end());
sum += (it)[0];
it[0] = -1 * it[0];
if (L[it[1]] != -1) {
s.erase({arr[L[it[1]]], L[it[1]]});
it[0] += arr[L[it[1]]];
if (L[L[it[1]]] != -1) R[L[L[it[1]]]] = it[1];
L[it[1]] = L[L[it[1]]];
}
if (R[it[1]] != -1) {
s.erase({arr[R[it[1]]], R[it[1]]});
it[0] += arr[R[it[1]]];
if (R[R[it[1]]] != -1) L[R[R[it[1]]]] = it[1];
R[it[1]] = R[R[it[1]]];
}
arr[it[1]] = it[0];
s.insert({arr[it[1]], it[1]});
cout << sum << "\n";
}
}
