/*
#include <stdio.h>
int main()
{
int n,i,max=0,max1=0,tmax=0,t=0,k=0,q,p;
int a[100001]={};
int b[100001]={};
int c[100001]={};
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(i==1)
{
max=a[i];
}
if(a[i]>=max)
{
max=a[i];
}
}
t=max;
for(i=1;i<=n;i++)
{
if(a[i]==max)
{
if(a[i-1]>=a[i+1])
{
t+=a[i-1];
q=-1;
}
else
{
t+=a[i+1];
q=1;
}
}
else
{
if(q==1)
{
t+=a[i+1];
}
else
{
t+=a[i-1];
}
}
b[i]=t;
k++;
}
tmax=b[1];
for(i=1;i<=k;i++)
{
if(b[i]>=tmax)
{
tmax=b[i];
}
}
for(i=1;i<=n;i++)
{
if(a[i]==max)
{
if(a[i-1]>=a[i+1])
{
t+=a[i-1];
q=1;
}
else
{
t+=a[i+1];
q=-1;
}
}
else
{
if(q==1)
{
t+=a[i+1];
}
else
{
t+=a[i-1];
}
}
c[i]=t;
k++;
}
max1=c[1];
for(i=1;i<=k;i++)
{
if(b[i]>=max1)
{
max1=c[i];
}
}
k=0;
if(max1<0)
{
printf("%d",tmax);
}
else
{
if(tmax<0)
{
printf("%d",max1);
}
else
{
printf("%d",tmax+max1-n);
}
}
}
*/
/*
#include <stdio.h>
int a[201]={};
int b[101][101]={};
int n;
void dfs(int c)
{
int i;
for(i=1;i<=n;i++)
{
if(b[c][i]==1&&a[i]!=1)
{
a[i]=1;
dfs(i);
}
}
}
int main()
{
int m,i,j,k,l,t=0;
scanf("%d %d",&n, &m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&k,&l);
b[k][l]=1;
b[l][k]=1;
}
dfs(1);
for(i=1;i<=n;i++)
{
if(a[i]==1)
{
t++;
}
}
printf("%d",t-1);
}
*/
/*
#include <stdio.h>
int a[26][26]={};
int b[100000]={};
int n,t=0;
void dfs(int x, int y)
{
if(x<1||y<1||x>n||y>n||a[x][y]!=1) return ;
a[x][y]=-1;
t++;
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
void swap(int x, int y)
{
int v=b[x];
b[x]=b[y];
b[y]=v;
}
void qs(int s, int e)
{
int p=s, l=s, h=e+1;
if(s>=e) return ;
do
{
do
{l++;
}while(b[p]>b[l]);
do
{h--;
}while(b[p]<b[h]);
if(l<h) swap(l,h);
}while(l<h);
swap(h,p);
qs(s,h-1);
qs(h+1,e);
}
int main()
{
int i,j,d=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%1d",&a[i][j]);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][j]==1)
{
dfs(i,j);
d++;
b[d]=t;
t=0;
}
}
}
qs(1,d);
printf("%d\n",d);
for(i=1;i<=d;i++)
{
printf("%d\n",b[i]);
}
}
*/
/*
#include <stdio.h>
char a[101][101];
int w,h;
void dfs(int x, int y)
{
if(x<1||y<1||x>h||y>w||a[x][y]!='L') return ;
a[x][y]='.';
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
dfs(x+1,y+1);
dfs(x-1,y+1);
dfs(x+1,y-1);
dfs(x-1,y-1);
}
int main()
{
int i,j,t=0;
scanf("%d %d",&w,&h);
for(i=1;i<=h;i++)
{
for(j=1;j<=w;j++)
{
scanf(" %c",&a[i][j]);
}
}
for(i=1;i<=h;i++)
{
for(j=1;j<=w;j++)
{
if(a[i][j]=='L')
{
dfs(i,j);
t++;
}
}
}
printf("%d",t);
}
nypc
*/
/*
#include <stdio.h>
int main()
{
int n,i,m;
int a[100001]={};
int max[100001]={};
scanf("%d",&n);
max[0]=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(max[i-1]>=0)
{
max[i]+=max[i-1]+a[i];
}
else
{
max[i]+=a[i];
}
}
m=max[1];
for(i=1;i<=n;i++)
{
if(m<=max[i])
{
m=max[i];
}
}
printf("%d",m);
}
*/
/*
#include <stdio.h>
int main()
{
int n,i;
double a[100001]={};
double max[100001]={};
double m;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf",&a[i]);
if(max[i-1]>=1)
{
max[i]=max[i-1]*a[i];
}
else
{
max[i]=a[i];
}
}
m=max[1];
for(i=1;i<=n;i++)
{
if(m<=max[i])
{
m=max[i];
}
}
printf("%.3lf",m);
}
*/
/*
#include <stdio.h>
int a[8][8];
int t=0;
void dfs(int n, int x, int y)
{
if(x<1||y<1||x>7||y>7||a[x][y]!=n)
return ;
t++;
a[x][y]=-1;
dfs(n,x+1,y);
dfs(n,x-1,y);
dfs(n,x,y+1);
dfs(n,x,y-1);
}
int main()
{
int i,j,tot=0;
for(i=1; i<=7; i++)
{
for(j=1; j<=7; j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=1; i<=7; i++)
{
for(j=1; j<=7; j++)
{
if(a[i][j]==-1) continue;
dfs(a[i][j],i,j);
if(t>=3)
{
tot++;
}
t=0;
}
}
printf("%d",tot);
}
*/
/*
#include <stdio.h>
int b[101][101]={};
int c[100001]={};
int n,m,d=0;
void dfs(int x, int y)
{
if(x<1||y<1||x>m||y>n||b[x][y]!=0)
return ;
c[d]++;
b[x][y]=1;
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
void swap(int x, int y)
{
int v=c[x];
c[x]=c[y];
c[y]=v;
}
void qs(int s, int e)
{
int p=s, l=s, h=e+1;
if(s>=e) return ;
do
{
do
{l++;
}while(c[p]>c[l]);
do
{h--;
}while(c[p]<c[h]);
if(l<h) swap(l,h);
}while(l<h);
swap(h,p);
qs(s,h-1);
qs(h+1,e);
}
int main()
{
int k,lx,ly,x,y,i,j,l;
scanf("%d %d %d",&m,&n,&k);
for(i=0;i<k;i++)
{
scanf("%d %d %d %d",&lx,&ly,&x,&y);
for(j=ly+1;j<y+1;j++)
{
for(l=lx+1;l<x+1;l++)
{
b[j][l]=1;
}
}
}
for(j=1;j<=m;j++)
{
for(l=1;l<=n;l++)
{
if(b[j][l]==0)
{
d++;
dfs(j,l);
}
}
}
qs(1,d);
printf("%d\n",d);
for(i=1;i<=d;i++)
{
printf("%d ",c[i]);
}
}
*/