#include<stdio.h>
void merge(int arr[],int left,int mid,int right)
{
   int i=left,j=mid+1,k=0;
   int temp[right-left+1];
   
   while(i<=mid&&j<=right)
   {
       if(arr[i]<=arr[j])
       {
           temp[k++]=arr[i++];
       }
       else{
           temp[k++]=arr[j++];
       }
   }
   while(i<=mid)
   {
       temp[k++]=arr[i++];
   }
   while(j<=right)
  {
   temp[k++]=arr[j++];
  }
  for(i=left,k=0;i<=right;i++,k++)
  {
      arr[i]=temp[k];
  }
      
}
void mergesort(int arr[],int left,int right)
{
    if(left<right)
    {
        int mid=(left+right)/2;
        mergesort(arr,left,mid);
        mergesort(arr,mid+1,right);
        merge(arr,left,mid,right);
          
        
    }
}
int issorted(int arr[],int n)
{
    for(int i=0;i<n-1;i++)
    {
     if(arr[i]>arr[i+1])
     {
       return 0;
     }
    }
    return 1;
}
int mai()
{
    int n;
    scanf("%d",&n);
    
    if(n<1||n>100)
    {
        printf("Invalid input");
        return 0;
    }
    int arr[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
        if(n<1||n>100)
        printf("Invalid input");
        return 0;
    }
    int arr[i];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
     if(arr[i]<0||arr[i]>100)
        {
            printf("Invalid input");
            return 0;
        }
if(issorted(arr,n))
{
    printf("List is already sorted");
    return 0;
}

mergesort(arr,0,n-1);

for(int i=0;i<n;i++)
{
    printf("%d",arr[i]);
    if(i<n-1) 
    {
    printf(" ");
    }
}
return 0;
}