#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct cell
{
long long int pos,st,type,to;
bool operator<(const cell&a)const
{
return st<a.st;
}
};
mt19937 mt(time(nullptr));
long long int n,a[200005];
long long int sum[200005],otg,dp[2005][2005],ot[2005],oo[2005],lamp;
map<int,int>m;
priority_queue<cell>q;
void prec()
{
sum[1]=a[1];
for(int i=2; i<=n; i++)
{
sum[i]=sum[i-2]+a[i];
}
}
void er(int val)
{
if(m[val]==0)m.erase(val);
}
void merg(int a,int b)
{
m[b]=m[a];
m.erase(a);
}
void fix(int a)
{
m[a+1]=m[a]-1;
m.erase(a);
}
void check(cell&w)
{
auto up=m.upper_bound(w.pos);
if(m[m[w.pos]-2])
{
merg(m[w.pos]-2,w.pos);
}
else er(m[w.pos]-2);
if(up->second==w.pos+2)
{
merg(w.pos,up->first);
w.pos=up->first;
}
}
void add(cell w)
{
if(w.pos==n||m[w.pos]==1)return;
cell c;
c.pos=w.pos;
c.to=m[w.pos];
c.type=2;
c.st=sum[w.pos+1]-sum[w.pos]+sum[m[w.pos]-2];
if(m[w.pos]>2)c.st-=sum[m[w.pos]-3];
//cout<<c.pos<<" "<<c.to<<" "<<c.st<<" "<<c.type<<" "<<w.pos<<endl;
q.push(c);
}
void resh()
{
cell w;
int br=0;
while(q.size())
{
w=q.top();
q.pop();
if(w.type==1)
{
auto up=m.lower_bound(w.pos);
if(m[w.pos-1]||(up!=m.end()&&(up->second==w.pos+1||(up->second<=w.pos&&up->first>=w.pos))))
{
er(w.pos-1);
continue;
}
er(w.pos-1);
otg+=w.st;
m[w.pos]=w.pos;
check(w);
}
if(w.type==2)
{
if(m[w.pos]!=w.to)
{
er(w.pos);
continue;
}
otg+=w.st;
fix(w.pos);
w.pos++;
check(w);
}
add(w);
br++;
if(otg!=ot[br])lamp=1;
oo[br]=otg;
}
}
void make_dp()
{
dp[1][1]=a[1];
dp[2][1]=max(a[1],a[2]);
ot[1]=dp[2][1];
for(int i=3;i<=n;i++)
{
for(int j=1;j<=(i+1)/2;j++)
{
dp[i][j]=max(dp[i-1][j],max(dp[i-2][j-1],dp[i-3][j-1])+a[i]);
ot[j]=max(ot[j],dp[i][j]);
}
}
}
void read()
{
cell c;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
c.pos=i;
c.st=a[i];
c.type=1;
c.to=0;
q.push(c);
}
//cout<<endl;
prec();
//make_dp();
resh();
for(int i=1;i<=(n+1)/2;i++)
{
cout<<oo[i]<<endl;
}
cout<<endl;
}
void clea()
{
while(q.size())q.pop();
m.clear();
otg=0;
for(int i=1;i<=n;i++)
{
ot[i]=0;
oo[i]=0;
for(int j=1;j<=n;j++)dp[i][j]=0;
sum[i]=0;
a[i]=0;
}
}
void test()
{
n=6;
cell c;
for(int j=1;j<=1000000;j++)
{
for(int i=1;i<=n;i++)
{
a[i]=mt()%100+1;
c.pos=i;
c.st=a[i];
c.type=1;
c.to=0;
q.push(c);
}
prec();
make_dp();
resh();
if(lamp)
{
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
for(int i=1;i<=(n+1)/2;i++)
{
cout<<ot[i]<<" "<<oo[i]<<endl;
}
return;
}
clea();
}
}
int main()
{
speed();
read();
//test();
return 0;
}
