#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N=2e3+5;
const ll INF=1e18;
int n;
ll a[N], l[N], r[N], vis[N];
priority_queue<pair<ll, int>> pq;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=1; i<=n; i++) {
cin >> a[i];
pq.push({a[i], i});
l[i]=i-1, r[i]=i+1;
}
l[0]=0, r[n+1]=n+1;
a[0]=-INF, a[n+1]=-INF;
ll ans=0;
for(int i=1; i<=(n+1)/2; i++) {
while(vis[pq.top().second])
pq.pop();
auto [val, id]=pq.top();
pq.pop();
ans+=val;
a[id]=a[l[id]]+a[r[id]]-a[id];
vis[l[id]]=vis[r[id]]=1;
r[id]=r[r[id]];
l[id]=l[l[id]];
l[r[id]]=r[l[id]]=id;
pq.push({a[id], id});
cout << ans << endl;
}
return 0;
}
