/*
3701
#include <stdio.h>
void p(int n)
{
int i,j;
long long int arr[51][51]={};
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
if(j==1||j==i)
{
arr[i][j]=1;
}
else
{
arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
}
printf("%lld ", arr[i][j]);
}
printf("\n");
}
return;
}
int main()
{
int n;
scanf("%d", &n);
p(n);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,j,arr[100001],max=-1001,memo[100001]={};
scanf("%d", &n);
for(i=1; i<=n; i++)
{
scanf("%d", &arr[i]);
}
for(i=1;i<=n;i++)
{
if(arr[i]>memo[i-1]+arr[i])
{
memo[i]=arr[i];
}
else
{
memo[i]=memo[i-1]+arr[i];
}
}
for(i=1;i<=n;i++)
{
if(memo[i]>max)
{
max=memo[i];
}
}
printf("%d", max);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i,j,n,t;
int temp=0,memo[100001]={};
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%d", &t);
memo[t]++;
}
for(i=0;i<=100000;i++)
{
for(j=1; j<=memo[i]; j++)
{
printf("%d ", i);
}
}
return 0;
}
*/