#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];
}
auto f = [&](auto f, int L, int R, int ls, int rs) -> vector<ll>{
if(L == R){
if(ls != rs){
return {-INF, -INF};
}
if(ls == 0){
return {0, -INF};
}
if(ls == 1){
return {-INF, a[L]};
}
}
int M = (L+R)/2;
vector<ll> c(R-L+2), t;
for(int rs1 = 0; rs1 <= 1; rs1++){
for(int ls2 = 0; ls2 <= 1; ls2++){
if((rs1&ls2) == 0){
t = concave_max_plus_convolution<ll>(f(f, L, M, ls, rs1), f(f, M+1, R, ls2, rs));
for(int i = 0; i < (int)t.size(); i++){
c[i] = max(c[i], t[i]);
}
}
}
}
return c;
};
vector<ll> ans(n+1), t;
for(int ls = 0; ls <= 1; ls++) for(int rs = 0; rs <= 1; rs++){
t = f(f, 1, n, ls, rs);
for(int i = 1; i <= (n+1)/2; i++){
ans[i] = max(ans[i], t[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();
}
