#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOD(i, r, l) for (int i = (r), _l = (l); i >= _l; i--)
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define Konosuba tuple<int , int , int, int>
#define fi first
#define se second
const int N = 3e5 + 5;
const int MOD = 1e9 + 7;
const int block = 330;
const int LOG = 30;
const int MAXN = 1e6 + 1;
const int INF = 1e14;
const int base = 311;
template<class A, class B>
bool umin(A& var, const B& val){ return (val < var) ? (var = val, true) : false; }
template<class A, class B>
bool umax(A& var, const B& val){ return (var < val) ? (var = val, true) : false; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class X, class Y> int random(const int& l, const int& r) {
return uniform_int_distribution<int>(l,r)(rng);
}
priority_queue<pii , vector<pii>> pq;
int n;
int a[N];
int L[N] , R[N];
int check[N];
void update(int u){
check[u] = 1;
L[R[u]] = L[u];
R[L[u]] = R[u];
}
void solve(void){
cin >> n;
FOR(i , 1 , n) {
cin >> a[i];
L[i] = i - 1; R[i] = i + 1;
pq.push(make_pair(a[i] , i));
}
a[0] = -INF , a[n + 1] = -INF;
int res = 0;
FOR(i , 1 , (n + 1) / 2){
while(pq.size() && check[pq.top().second]) pq.pop();
res += pq.top().first; cout << res << endl;
int u = pq.top().second;
pq.pop();
a[u] = a[L[u]] + a[R[u]] - a[u];
pq.push({a[u], u});
int tmpl = L[u] , tmpr = R[u];
update(tmpl);
update(tmpr);
}
}
signed main(void) {
if (fopen("smod.INP", "r")) {
freopen("smod.INP", "r", stdin);
freopen("smod.OUT", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int testCase = 1; //cin >> testCase;
FOR(i , 1 , testCase){
solve();
}
cerr << "Time elapsed: " << TIME << "s.\n";
return (0);
}
