// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int mxN = 5e5+7 , Inf = 1e17;
int n , v[mxN] , l[mxN],r[mxN];
bool mrk[mxN];
priority_queue<pii> pq;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1; i<=n; i++)
cin >> v[i];
v[0] = v[n+1] = -Inf;
for (int i=1; i<=n; i++)
l[i]=i-1 , r[i]=i+1;
for (int i=1; i<=n; i++)
pq.push({ v[i] , i });
int k = n+1>>1 , out = 0;
for (int i=1; i<=k; i++)
{
while (!pq.empty())
{
auto [q , id] = pq.top();
pq.pop();
if (mrk[ id ]) continue;
out += q;
int lc = l[id] , rc = r[id];
mrk[lc] = mrk[rc] = true;
v[id] = v[lc]+v[rc] - v[id];
pq.push({ v[id] , id });
l[id] = l[lc]; r[id] = r[rc];
r[l[id]] = id; l[r[id]] = id;
break;
}
cout << out << '\n';
}
}
