#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; }