#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define V1 vector<ll>
#define V2 vector<V1>
#define V3 vector<V2>
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n; cin>>n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++){
cin>>a[i];
}
vector<ll> f(n + 1), s;
function<V3(int, int)> solve = [&](int l, int r){
if (l == r){
V3 dp; dp.resize(2);
for (int i = 0; i < 2; i++){
dp[i].resize(2);
}
dp[0][0] = {a[l]};
return dp;
}
int m = (l + r) / 2;
V3 a = solve(l, m), b = solve(m + 1, r), dp;
dp.resize(2);
for (int i = 0; i < 2; i++){
dp[i].resize(2);
}
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
for (int t = 1; t <= (r - l + 1); t++){
f[t] = -1;
}
for (int t = 0; t < 2; t++){
int i1 = 0, i2 = 0; s.clear();
while (i1 < a[i][t].size() || i2 < b[!t][j].size()){
if (i1 == a[i][t].size()){
s.pb(b[!t][j][i2++]);
continue;
}
if (i2 == b[!t][j].size()){
s.pb(a[i][t][i1++]);
continue;
}
if (a[i][t][i1] > b[!t][j][i2]){
s.pb(a[i][t][i1++]);
}
else {
s.pb(b[!t][j][i2++]);
}
}
ll sum = 0;
for (int x = 0; x < s.size(); x++){
sum += s[x];
f[x + 1] = max(f[x + 1], sum);
}
}
for (int t = 1; t <= n; t++){
if (f[t] == -1) break;
dp[i][j].pb(f[t] - f[t - 1]);
}
}
}
return dp;
};
V3 dp = solve(1, n);
ll out = 0;
for (ll i: dp[0][0]){
out += i;
cout<<out<<"\n";
}
}
