import java.io.*;

class sort
{
      String str;
      int size,sortArr[];
      
      publicvoid getdata()
      {
             System.out.print("Enter how many data you want to enter : ");
             System.out.flush();
             try{
                 BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));
                 str=obj.readLine();
                 size=Integer.parseInt(str);
                 sortArr=newint[size];
                 for(int i=0;i<size;i++)
                   {
                       System.out.print("Enter element at "+(i+1)+"th position  :  ");
                       System.out.flush();
                       str=obj.readLine();
                       sortArr[i]=Integer.parseInt(str);
                   }
                }
            catch(Exception e)  {}
      }
                 
      publicvoid  InsSort()
      {
            System.out.println("=====INSERTION SORT=====\n");
            getdata();
            int i,j=0,temp=0;
                for(i=0;i<size;i++)
                    {
                     if(sortArr[i]<sortArr[i-1])
                     {
                        temp=sortArr[i];
                       for(j=i-1;j>=0;j--)
                        {
                           sortArr[j+1]=sortArr[j];
                           if(sortArr[j-1]<=temp || j==0)
                              break;
                        }
                     }
                    sortArr[j]=temp;
                  }
            display();
        }    

    publicvoid display()
    {
         System.out.println("\nAfter Sorting");
         for(int i=0;i<size;i++)
              System.out.println(sortArr[i]);
    }
}


class InsSort 
{
    publicstaticvoid main(String args[]) 
    {
          sort ob1=new sort();
          ob1.InsSort();
    }
}