#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define ft first
#define sc second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int, int>
#define vi vector<int>
#define tii tuple<int, int, int>
#define tiii tuple<int, int, int, int>
#define tiiii tuple<int, int, int, int, int>
#define vpi vector<pi>
#define vtii vector<tii>
#define vtiii vector<tiii>
const int N = (1 << 20), MOD = 1e9 + 7, INF = int(1e12);
vi dp[N][4];
int arr[N];
int gt(int x, vi &a){
if(x < 0) return 0;
if(x >= int(a.size())) return -INF;
return a[x];
}
void mrg(vi &x, vi &a, vi &b){
int akt = 0;
int l = 0, r = 0, n, m;
for(auto &i : x){
n = gt(l, a) - gt(l - 1, a); m = gt(r, b) - gt(r - 1, b);
if(l == int(a.size()) && r == int(b.size())) break;
if(n > m){
akt += n;
l++;
}else{
akt += m;
r++;
}
i = max(i, akt);
}
}
void rep(int u){
for(int i = 0; i < 4; i++){
while(!dp[u][i].empty() && dp[u][i].back() == 0) dp[u][i].pop_back();
}
}
void rec(int u, int l, int r, int n){
if(l > n || r < 1 || l > r) return;
int dl = r - l + 1;
for(int i = 0; i < 4; i++) dp[u][i].resize(dl);
if(l == r){
dp[u][3][0] = arr[l];
rep(u);
return;
}
rec(2 * u, l, (r + l) / 2, n);
rec(2 * u + 1, (l + r) / 2 + 1, r, n);
int x = 2 * u, y = 2 * u + 1;
mrg(dp[u][0], dp[x][0], dp[y][1]);
mrg(dp[u][0], dp[x][2], dp[y][0]);
mrg(dp[u][1], dp[x][1], dp[y][1]);
mrg(dp[u][1], dp[x][3], dp[y][0]);
mrg(dp[u][2], dp[x][0], dp[y][3]);
mrg(dp[u][2], dp[x][2], dp[y][2]);
mrg(dp[u][3], dp[x][1], dp[y][3]);
mrg(dp[u][3], dp[x][3], dp[y][2]);
rep(u);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
rec(1, 1, n, n);
for(int i = 0; i < (n + 1) / 2; i++) cout << dp[1][3][i] << "\n";
return 0;
}
