#include <bits/stdc++.h>
#define inf 200000000000000000
#define N 200050
#define f first
#define s second
using namespace std;
#define int long long
typedef pair<int, int> pii;
int n, k, v[N], ans, t = 0;
set < pii > pq, list;
struct linked_list
{
int esq[N], dir[N];
void clear()
{
memset(esq, 0, sizeof esq);
memset(dir, 0, sizeof dir);
}
void erase(int p)
{
if( p <= 0 || p > n ) return;
dir[esq[p]] = dir[p];
esq[dir[p]] = esq[p];
}
} L;
int32_t main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>v[i];
L.esq[i] = i - 1;
L.dir[i] = i + 1;
pq.insert({-v[i], i});
}
for(int i = 1; i <= ((n + 1)/2); i++)
{
auto it = pq.begin();
int x = -(*it).f, id = (*it).s;
int l = L.esq[id], r = L.dir[id];
L.erase(l), L.erase(r);
if(l > 0 && l <= n && r > 0 && r <= n) v[id] = -v[id] + v[l] + v[r];
else v[id] = -inf;
pq.erase({-x, id}), pq.erase({-v[l], l}), pq.erase({-v[r], r});
pq.insert({-v[id], id});
ans += x;
cout<<ans<<"\n";
}
}
