#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MASK(i) (1LL << (i))
#define GETBIT(i, msk) ((msk >> (i)) & 1)
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
using namespace std;
const int maxn = 2e5;
const int lim = 1e6;
const ll inf = 1e18;
ll max(ll a,ll b) {return (a > b ? a : b);}
ll min(ll a,ll b) {return (a < b ? a : b);}
ll gcd(ll a,ll b) {return __gcd(a, b);}
ll lcm(ll a,ll b) {return a / gcd(a, b) * b;}
int popcnt(ull n) {return __builtin_popcountll(n);}
template<class T1,class T2>
bool maximize(T1 &a,T2 b) {
if(a < b) {
a = b;
return 1;
}
return 0;
}
template<class T1,class T2>
bool minimize(T1 &a,T2 b) {
if(a > b) {
a = b;
return 1;
}
return 0;
}
int n;
ll diff[maxn + 5], lef[maxn + 5], rig[maxn + 5];
bool del[maxn + 5];
void solve() {
for(int i = 1; i <= n; ++i) {
lef[i] = i - 1;
rig[i] = i + 1;
}
priority_queue<pair<ll, int>> pq;
for(int i = 1; i <= n; ++i) pq.push(make_pair(diff[i], i));
ll sum = 0;
for(int t = 0; t < ((n + 1) >> 1); ++t) {
while(del[pq.top().se]) pq.pop();
int i = pq.top().se;
// cout<<t<<' '<<i<<'\n';
sum += pq.top().fi; pq.pop();
cout<<sum<<'\n';
ll ndiff = -diff[i] + (lef[i] > 0 ? diff[lef[i]] : -inf) +
(rig[i] <= n ? diff[rig[i]] : -inf);
diff[i] = ndiff;
pq.push(make_pair(diff[i], i));
if(lef[i] > 0) {
del[lef[i]] = 1;
lef[i] = lef[lef[i]];
rig[lef[i]] = i;
}
if(rig[i] <= n) {
del[rig[i]] = 1;
rig[i] = rig[rig[i]];
lef[rig[i]] = i;
}
}
return;
}
void input() {
cin>>n;
for(int i = 1; i <= n; ++i) cin>>diff[i];
return;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("ADN.inp", "r", stdin);
// freopen("ADN.out", "w", stdout);
input();
solve();
return 0;
}
