#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
#pragma optimize("PLEASE_GIVE_ACCEPTED")
#define int long long
using ll = long long;
using ii = pair<int,int>;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define pu emplace
#define pf emplace_front
#define sz(v) (int)(v.size())
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=a-1;i>=b;i--)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define ub upper_bound
#define dieded(k) do {cout<<k; return 0;} while(0)
// Ordered set
// https://codeforces.com/blog/entry/11080
using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
// Modular Arithmetic
template<int MOD> struct mint {
explicit operator ll() const {return v;}
mint(ll _v) {v=int32_t(_v%MOD); if(v<0) v+=MOD;}
mint() {v=0;}
mint& operator += (mint y) {v+=y.v; if(v>=MOD) v-=MOD; return *this;}
mint& operator -= (mint y) {v-=y.v; if(v<0) v+=MOD; return *this;}
mint& operator *= (mint y) {v=int32_t((1LL*v*y.v)%MOD); return *this;}
friend mint operator + (mint x, mint y) {return x+=y;}
friend mint operator - (mint x, mint y) {return x-=y;}
friend mint operator * (mint x, mint y) {return x*=y;}
friend mint pow (mint base, int expo) {
expo %= (MOD-1);
if(expo<0) expo+=(MOD-1);
return internal_pow(base, expo);
}
private:
int32_t v;
friend mint internal_pow(mint base, int expo) {
if(expo==0) return 1;
return internal_pow(base * base, expo >> 1) * (expo & 1 ? base : 1);
}
};
using mt1 = mint<998244353>;
using mt2 = mint<1000000007>;
#ifdef DEBUG
#define debug if(1)
#define RTEfind cout<<"RTE check (line "<<__LINE__<<")\n"
#define state(...) do {cout<<"Line "<<__LINE__<<": "; printf(__VA_ARGS__);} while(0)
#else
#define debug if(0)
#define RTEfind 42
#define state(...) 69
#endif
inline int readInt() {
int x; cin >> x;
return x;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int32_t main() {
#ifdef DEBUG
auto programstarttime=high_resolution_clock::now();
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif
int n = readInt();
priority_queue<ii> pq;
bool bad[n+1];
REP(i,1,n+1) bad[i]=0;
int a[n+2], nxt[n+2], prv[n+2];
nxt[0]=prv[0]=nxt[n+1]=prv[n+1]=0;
int ans=0;
a[0]=a[n+1]=-1210201012102010;
REP(i,1,n+1) pq.pu(a[i]=readInt(),i), nxt[i]=i+1, prv[i]=i-1;
REP(i,0,((n+1)>>1)) {
while(bad[pq.top().se]) pq.pop();
ii x = pq.top(); pq.pop();
cout<<(ans+=x.fi)<<"\n";
pq.pu(a[x.se]=a[prv[x.se]]+a[nxt[x.se]]-a[x.se],x.se);
bad[prv[x.se]]=bad[nxt[x.se]]=1;
prv[nxt[x.se]=nxt[nxt[x.se]]]=x.se; nxt[prv[x.se]=prv[prv[x.se]]]=x.se;
}
#ifdef DEBUG
auto programendtime=high_resolution_clock::now();
duration<long double, milli> programdur=programendtime-programstarttime;
cout<<"\nProgram took "<<programdur.count()<<" milliseconds";
#endif
}
