#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
vector<int> a(n + 2), l(n + 2), r(n + 2);
priority_queue<pair<int, int>> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
l[i] = i - 1, r[i] = i + 1;
q.emplace(a[i], i);
}
l[n + 1] = n;
r[0] = 1;
const int oo = 1e18;
a[0] = a[n + 1] = -oo;
int ans = 0;
vector<bool> used(n + 2);
for(int t = 1; t <= (n + 1) / 2; t++) {
while(used[q.top().second]) {
q.pop();
}
auto [add, i] = q.top();
q.pop();
ans += add;
a[i] = a[l[i]] + a[r[i]] - a[i];
q.emplace(a[i], i);
used[l[i]] = used[r[i]] = 1;
l[i] = l[l[i]];
r[l[i]] = i;
r[i] = r[r[i]];
l[r[i]] = i;
cout << ans << '\n';
}
}
