#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(998244353)
#define int ll
using namespace std;
template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2>
void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}
template<class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}
template<class T>
void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
ll calc(vector<int> arr, int k){
priority_queue<pair<int, int>> pq;
int n = sz(arr);
vector<bool> isDel(n, false);
vector<int> nxt(n), prv(n);
for(int i = 0; i < n; i++){
pq.push({arr[i], i});
nxt[i] = i + 1;
prv[i] = i - 1;
}
int cur = 0;
for(int i = 1; i <= k; i++){
while(isDel[pq.top().se]) pq.pop();
auto t = pq.top();
pq.pop();
cur += t.fi;
cout << cur << '\n';
arr[t.se] = - arr[t.se] + (nxt[t.se] < n ? arr[nxt[t.se]] : -oo) + (prv[t.se] >= 0 ? arr[prv[t.se]] : -oo);
pq.push({arr[t.se], t.se});
if(prv[t.se] >= 0){
isDel[prv[t.se]] = true;
prv[t.se] = prv[prv[t.se]];
if(prv[t.se] >= 0) nxt[prv[t.se]] = t.se;
}
if(nxt[t.se] < n){
isDel[nxt[t.se]] = true;
nxt[t.se] = nxt[nxt[t.se]];
if(nxt[t.se] < n) prv[nxt[t.se]] = t.se;
}
}
return cur;
}
void solve(){
int n; cin >> n;
vector<int> a;
for(int i = 0; i < n; i++){
int x; cin >> x;
a.push_back(x);
}
calc(a, (n + 1) / 2);
// int n, k; cin >> n >> k;
// string s; cin >> s;
//
// vector<int> ord;
// int ans = INF;
//
// int d = 0;
// for(int i = 0; i < sz(s); i++){
// d++;
// if(i + 1 == sz(s) || s[i] != s[i + 1]){
// ord.push_back(d);
// d = 0;
// }
// }
//
// if(sz(ord) <= k){
// cout << 0 << '\n';
// return;
// }
//
// k = sz(ord) - k;
//
// if(k & 1){
// vector<int> tmp1;
// for(int i = 2; i + 1 < sz(ord); i++) tmp1.push_back(ord[i]);
// minimize(ans, ord[0] + calc(tmp1, k / 2));
//
// vector<int> tmp2;
// for(int i = 1; i + 2 < sz(ord); i++) tmp2.push_back(ord[i]);
// minimize(ans, ord.back() + calc(tmp2, k / 2));
// }
// else if(k >= 2) {
// vector<int> tmp1;
// for(int i = 2; i + 2 < sz(ord); i++) tmp1.push_back(ord[i]);
// minimize(ans, ord[0] + ord.back() + calc(tmp1, (k - 2) / 2));
//
// vector<int> tmp2;
// for(int i = 1; i + 1 < sz(ord); i++) tmp2.push_back(ord[i]);
// minimize(ans, calc(tmp2, k / 2));
// }
//
// cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("partner.inp","r",stdin);
// freopen("partner.out","w",stdout);
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
