#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, l[200002], r[200002], p;
long long a[200002], x, res;
bool covered[200002];
priority_queue<pair<long long, int>> pq;
int main()
{
setup();
cin >> n;
l[0] = 0;
r[n + 1] = n + 1;
a[0] = a[n + 1] = -1e18;
for (int i = 1; i <= n; ++i)
{
l[i] = i - 1;
r[i] = i + 1;
cin >> a[i];
pq.push({a[i], i});
}
for (int i = 1; i <= (n + 1) / 2; ++i)
{
while (covered[pq.top().second])
{
pq.pop();
}
x = pq.top().first;
p = pq.top().second;
pq.pop();
res += x;
a[p] = a[l[p]] + a[r[p]] - a[p];
covered[l[p]] = covered[r[p]] = true;
r[p] = r[r[p]];
l[p] = l[l[p]];
l[r[p]] = r[l[p]] = p;
pq.push({a[p], p});
cout << res << "\n";
}
return 0;
}
