#include<iostream>
 
using namespace std;
 
void insertion_sort(int n, int arr[])
{
   cout<<"insertion sort"<<endl;
   int cnt_comp=0,cnt_ex=0;
   for(int j=1;j<n;j++)
   {
      int key=arr[j];
      int i=j-1;
      while(i>=0 && arr[i]>key)
      {
         arr[i+1]=arr[i];
         i--;
         cnt_comp++;
         cnt_ex++;
      }
      cnt_comp++;
      arr[i+1]=key;
   }
 
   cout<<"Number of comparisons:"<<cnt_comp<<endl;
   cout<<"Number of exchange:"<<cnt_ex<<endl;
}
 
int main()
{
   int n=100;
   int arr[100];
   //int arr[5]={5,3,6,7,1};
 
   //insertion_sort(n,arr);
 
   for(int i=0;i<100;i++)
   {
      cout<<arr[i]<<" ";
 
   }
}
 

CiNpbmNsdWRlPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgaW5zZXJ0aW9uX3NvcnQoaW50IG4sIGludCBhcnJbXSkKewogICBjb3V0PDwiaW5zZXJ0aW9uIHNvcnQiPDxlbmRsOwogICBpbnQgY250X2NvbXA9MCxjbnRfZXg9MDsKICAgZm9yKGludCBqPTE7ajxuO2orKykKICAgewogICAgICBpbnQga2V5PWFycltqXTsKICAgICAgaW50IGk9ai0xOwogICAgICB3aGlsZShpPj0wICYmIGFycltpXT5rZXkpCiAgICAgIHsKICAgICAgICAgYXJyW2krMV09YXJyW2ldOwogICAgICAgICBpLS07CiAgICAgICAgIGNudF9jb21wKys7CiAgICAgICAgIGNudF9leCsrOwogICAgICB9CiAgICAgIGNudF9jb21wKys7CiAgICAgIGFycltpKzFdPWtleTsKICAgfQoKICAgY291dDw8Ik51bWJlciBvZiBjb21wYXJpc29uczoiPDxjbnRfY29tcDw8ZW5kbDsKICAgY291dDw8Ik51bWJlciBvZiBleGNoYW5nZToiPDxjbnRfZXg8PGVuZGw7Cn0KCmludCBtYWluKCkKewogICBpbnQgbj0xMDA7CiAgIGludCBhcnJbMTAwXTsKICAgLy9pbnQgYXJyWzVdPXs1LDMsNiw3LDF9OwoKICAgLy9pbnNlcnRpb25fc29ydChuLGFycik7CgogICBmb3IoaW50IGk9MDtpPDEwMDtpKyspCiAgIHsKICAgICAgY291dDw8YXJyW2ldPDwiICI7CgogICB9Cn0K