/*
#include <stdio.h>
int a[500000],j=1;
void swap(int x, int y)
{
int t=a[x];
a[x]=a[y];
a[y]=t;
}
void qs(int s, int e)
{
int p=s, l=s, h=e+1;
if(s>=e) return ;
do
{
do
{l++;
}while(a[p]>a[l]);
do
{h--;
}while(a[p]<a[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,c=0,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
qs(1,n);
for(i=1;i<=n;i++)
{
printf("%d\n",a[i]);
}
return 0;
}
*/
/*
#include <stdio.h>
int a[50001]= {};
int c[50001]= {};
void swap(int x, int y)
{
int t=c[x];
c[x]=c[y];
c[y]=t;
}
void qs(int s, int e)
{
int p=s, l=s, h=e+1;
if(s>=e)
return ;
do
{
do
{
l++;
}
while(c[l]<c[p]);
do
{
h--;
}
while(c[h]>c[p]);
if(l<h)
swap(l,h);
}
while(l<h);
swap(h,p);
qs(1,h-1);
qs(h+1,e);
}
int bs(int n, int s, int e)
{
int m;
m = (s+e)/2;
if(s>e)
return -1;
if(c[m]<n)
{
bs(n,m+1,e);
}
else if(c[m]>n)
{
bs(n,1,m-1);
}
else
{
return m-1;
}
}
int main()
{
int n,i,j;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d",&a[i]);
c[i]=a[i];
}
qs(1,n);
for(i=1; i<=n; i++)
{
printf("%d ",bs(a[i],1,n));
}
}
*/
/*
#include <stdio.h>
int c[50001]= {};
int bs(int n, int s, int e)
{
int m = (s+e)/2;
if(s>e)
return 0;
if(c[m]<n)
{
bs(n,m+1,e);
}
else if(c[m]>n)
{
bs(n,0,m-1);
}
else
{
return m;
}
}
int main()
{
int n,i,j,t,l=1,max=0;
int a[500001]= {};
int b[50001]= {};
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d",&t);
b[i]=t;
a[t]++;
if(t>max) max=t;
}
j=0;
for(i=0; i<=t; i++)
{
if(a[i]!=0)
{
while(a[i]>0)
{
c[j++]=i;
a[i]--;
}
}
}
for(i=0;i<n;i++)
{
// printf("%d ",bs(b[i],0,n-1));
printf("%d ",c[i]);
}
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,j,k,a[101][101]={},x,y,l=0;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d %d",&x,&y);
for(j=y;j<=y+9;j++)
{
for(k=x;k<=x+9;k++)
{
a[j][k]=1;
}
}
}
for(i=1;i<=100;i++)
{
for(j=1;j<=100;j++)
{
if(a[i][j]==1)
{
l++;
}
}
}
printf("%d",l);
}
*/
/*
#include <stdio.h>
int main()
{
int n,k,i,a[100000],j,m=0,l=0,b;
scanf("%d",&n);
scanf("%d",&k);
for(i=1; i<=n; i++)
{
scanf("%d",&a[i]);
}
for(b=1; b<=n; b++)
{
for(i=1; i<=n-b+1; i++)
{
for(j=i; j<=i+b-1; j++)
{
m+=a[j];
}
if(m==k)
{
l++;
}
m=0;
}
}
printf("%d",l);
}
*/