#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
int32_t main(){
int n;
cin>>n;
vector <int> l(n+5), r(n+5), val(n+5, LLONG_MIN/5);
vector<bool> del(n+5, 0);
priority_queue<pii> pq;
for (int i=1; i<=n; ++i){
cin>>val[i];
pq.push(mp(val[i], i));
l[i]=i-1, r[i]=i+1;
}
int ans=0;
for (int j=0; j<(n+1)/2; ++j){
while (del[pq.top().second])pq.pop();
int i=pq.top().second, cval=pq.top().first;
pq.pop();
ans+=cval;
val[i]=val[l[i]]+val[r[i]]-val[i];
pq.push(mp(val[i], i));
del[l[i]]=del[r[i]]=1;
l[i]=l[l[i]], r[l[i]]=i, r[i]=r[r[i]], l[r[i]]=i;
cout<<ans<<"\n";
}
}
