#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
template <class T>
vector<T> concave_max_plus_convolution(const vector<T> &a, const vector<T> &b){
int n = a.size(), m = b.size();
vector<T> c(n+m-1);
c[0] = a[0] + b[0];
vector<T> slope;
int j = 1, N = 0;
for(int i = 1; i < n; i++){
while(j < m && b[j] - b[j-1] > a[i] - a[i-1]){
N++;
c[N] = c[N-1] + b[j] - b[j-1];
j++;
}
N++;
c[N] = c[N-1] + a[i] - a[i-1];
}
while(j < m){
N++;
c[N] = c[N-1] + b[j] - b[j-1];
j++;
}
return c;
}
void solve(){
int n;
cin >> n;
vector<ll> a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int cnt = 0;
auto f = [&](auto f, int L, int R) -> array<vector<ll>, 4>{
cnt++;
//cerr<< L << " " << R << " " << cnt << "\n";
if(L == R){
array<vector<ll>, 4> res;
res[0] = {0, -INF};
res[1] = res[2] = {-INF, -INF};
res[3] = {-INF, a[L]};
return res;
}
int M = (L+R)/2;
array<vector<ll>, 4> fL = f(f, L, M), fR = f(f, M+1, R), res;
for(int l = 0; l <= 1; l++){
for(int r = 0; r <= 1; r++){
vector<ll> c(R-L+2, -INF);
for(int ls = 0; ls <= 1; ls++){
for(int rs = 0; rs <= 1; rs++){
if(ls && rs) continue;
vector<ll> t = concave_max_plus_convolution(fL[l<<1 | rs], fR[ls<<1 | r]);
for(int i = 0; i < (int)t.size(); i++){
c[i] = max(c[i], t[i]);
}
}
}
res[l<<1 | r] = c;
}
}
return res;
};
vector<ll> ans(n+1, 0);
array<vector<ll>, 4> c;
c = f(f, 1, n);
for(int s = 0; s < 4; s++){
for(int i = 1; i <= (n+1)/2; i++){
ans[i] = max(ans[i], c[s][i]);
}
}
for(int i = 1; i <= (n+1)/2; i++){
cout << ans[i] << "\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
