#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cerr<<#x << " : " << x << "\n";
using namespace std ;
const ll maxn = 4e5 + 10 , mod = 1e9 + 7 , inf =1e14 ;
int a[maxn];
vector<ll> comb(vector<ll> a, vector<ll> b){
vector <ll>res(sz(a) + sz(b)-1);
int id0 = 0 , id1 =0 ;
while(!(id0 == sz(a)-1 && id1 == sz(b)-1)){
res[id0+id1] = a[id0] + b[id1] ;
if(id0!=sz(a)-1 && (id1==sz(b)-1 || a[id0+1]-a[id0] > b[id1+1]-b[id1])){
id0++;
}else{
id1++;
}
}
res[sz(a)+sz(b)-2] = a.back() + b.back() ;
return res;
}
vector<vector<vector<ll>>> slv(int l, int r){
if(l + 1 == r){
return {{{0, -inf}, {-inf, -inf}}, {{-inf, -inf}, {-inf, a[l]}}};
}
int mid = (l + r)>>1;
auto resl = slv(l, mid), resr = slv(mid, r);
int len = (r - l + 1)/2 + 1;
vector<vector<vector<ll>>> res(2, vector<vector<ll>>(2));
rep(i,0,1){
rep(j,0,1){
res[i][j] = comb(resl[i][0], resr[0][j]);
rep(t,0,1){
vector<ll> tmp = comb(resl[i][t], resr[t^1][j]);
rep(k,0,sz(tmp)-1) res[i][j][k] = max(res[i][j][k], tmp[k]);
}
res[i][j].resize(len);
}
}
return res;
}
int main(){
ios::sync_with_stdio(0) ;cin.tie(0);
int n; cin >> n;
rep(i,0,n-1) cin >> a[i];
auto res = slv(0, n);
vector<ll> ans = res[0][0];
rep(i,0,1) rep(j,0,1){
rep(k,0,sz(ans)-1) ans[k] = max(ans[k], res[i][j][k]);
}
rep(i,1,((n+1)>>1)){
cout << ans[i] << '\n';
}
return 0-0;
}
