/*
Author : DeMen100ns (Vo Khac Trieu)
School: University of Science, VNU-HCM
Aim:
- International Grandmaster Codeforces (2600)
- ICPC World Final 2025
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long INF = numeric_limits<long long>::max() / 8;
const int INF_int = 1e9 + 7;
vector <int> max_plus(vector <int> a, vector <int> b){
// for(int i : a) cout << i << " ";
// cout << "+ ";
// for(int i : b) cout << i << " ";
// cout << "= ";
int n = a.size(), m = b.size();
vector <int> ans(n + m - 1, 0);
ans[0] = a[0] + b[0];
for(int k = 1, i = 0, j = 0; k < n + m - 1; ++k){
int option = -1;
if (i == n - 1){
option = 1;
}
else if (j == m - 1){
option = 0;
}
else{
if (a[i + 1] - a[i] > b[j + 1] - b[j]){
option = 0;
} else option = 1;
}
if (!option){
ans[k] = ans[k - 1] + a[i + 1] - a[i];
++i;
} else {
ans[k] = ans[k - 1] + b[j + 1] - b[j];
++j;
}
}
// for(int i : ans) cout << i << " "; cout << endl;
return ans;
}
array<vector<int>, 4> dnc(vector <int> &a, int l, int r){
if (l == r){
return array<vector<int>, 4>({vector<int>({0}), vector<int>({-INF}),
vector<int>({-INF}), vector<int>({-INF, a[l]})});
}
int mid = (l + r) >> 1;
array<vector<int>, 4> L = dnc(a, l, mid), R = dnc(a, mid + 1, r);
//cout << l << "->" << r << ":" << endl;
array<vector<int>, 4> res;
for(int l = 0; l <= 1; ++l){
for(int r = 0; r <= 1; ++r){
vector <int> ans = {};
for(int midl = 0; midl <= 1; ++midl){
for(int midr = 0; midr <= 1; ++midr){
if (midl && midr) continue;
// cout << l << "-" << midl << " + " << midr << "-" << r << endl;
vector <int> F = max_plus(L[l << 1 | midl], R[midr << 1 | r]);
for(int i = 0; i < F.size(); ++i){
if (i >= ans.size()) ans.push_back(F[i]);
else ans[i] = max(ans[i], F[i]);
}
}
}
res[l << 1 | r] = ans;
}
}
return res;
}
void solve(){
int n; cin >> n;
vector <int> a(n);
for(int &x : a) cin >> x;
array<vector<int>, 4> ans = dnc(a, 0, n - 1);
for(int i = 1; i <= (n + 1) / 2; ++i){
int res = -1;
for(int j = 0; j < 4; ++j){
if (ans[j].size() > i) res = max(res, ans[j][i]);
}
if (res == -1) res = 0;
cout << res << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t = 1; // cin >> t;
for(int test = 1; test <= t; ++test){
solve();
}
}
