#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define all(x) (x).begin(),(x).end()
#define vll vector<long long>
#define pvll pair<vll,vll>
#define x first
#define y second
//first index=left
//1=excluding
//{{{},{}},{{},{}}};
void gtmx(ll&a,ll b){if(b>a)a=b;}
vll get1(vll f,vll s){
if(!s.size())return f;if(!f.size())return s;
int n=f.size()+s.size();
vll toz(n);
for(int i=0;f.size()>i;++i)gtmx(toz[i],f[i]);
for(int i=0;s.size()>i;++i)gtmx(toz[i],s[i]);
int nf=1;
for(int i=2;n>=i;++i){
if(i-nf>s.size())++nf;
while(nf>1&&i-nf<s.size()&&f[nf-1]+s[i-nf-1]<f[nf-2]+s[i-nf])--nf;
while(nf<i-1&&nf<f.size()&&f[nf-1]+s[i-nf-1]<f[nf]+s[i-nf-2])++nf;
gtmx(toz[i-1],f[nf-1]+s[i-nf-1]);
if(i==4&&toz[i-1]>4000000000){
cout<<"hi\n";
}
}
return toz;
}
vll uni(vll f,vll s){
if(s.size()>f.size())swap(s,f);
for(int i=0;s.size()>i;++i)gtmx(f[i],s[i]);
return f;
}
pair<pvll,pvll> rec (vector<int>&nuts,int st,int en){
if(en-st<=2){
if(en==st)return{{{(ll)nuts[st]},{}},{{},{}}};
if(en==st+1)return {{{max(nuts[st],nuts[en])},{nuts[st]}},{{nuts[en]},{}}};
return {{{max({nuts[st],nuts[st+1],nuts[en]}),nuts[st]+nuts[en]},{max(nuts[st],nuts[st+1])}},{{max(nuts[st+1],nuts[en])},{nuts[st+1]}}};
}
int g=(en+st)/2;
auto x1=rec(nuts,st,g);
auto x2=rec(nuts,g+1,en);
return{{uni(get1(x1.x.y,x2.x.x),get1(x1.x.x,x2.y.x)),
uni(get1(x1.x.y,x2.x.y),get1(x1.x.x,x2.y.y))
},{uni(get1(x1.y.y,x2.x.x),get1(x1.y.x,x2.y.x)),
uni(get1(x1.y.y,x2.x.y),get1(x1.y.x,x2.y.y))
}};
}
vector<long long> Nuts(int N, vector<int> nuts){
return rec(nuts,0,N-1).x.x;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
vector<int> nuts(n);
for(int i=0;i<n;i++) cin>>nuts[i];
vector<long long> ans = Nuts(n, nuts);
for(long long c : ans) cout<<c<<endl;
return 0;
}
