#include <stdio.h>
#include <iostream>
using namespace std;

#define MAX 255
int R[MAX];

void Insert_Sort(int n)
{  
    int i,j;
    for(i=2;i<=n;i++)  
      if(R[i]<R[i-1])
      {                        
        R[0]=R[i];
		j=i-1; /* R[0]是哨兵，且是R[i]的副本 */
        do{ /* 從右向左在有序區R[1．．i-1]中查找R[i]的插入位置 */
         R[j+1]=R[j]; /* 將關鍵字大于R[i]的記錄后移 */
         j--;
         }while(R[0]<R[j]);  /* 當R[i]≥R[j]時終止 */
        R[j+1]=R[0]; /* R[i]插入到正確的位置上 */
       }
}

void main()
{
	int i,n;
	cout << "Please input total element number of the sequence:" ;
	cin >> n;
	if(n<=0||n>MAX)
	{
		cout << "n must more than 0 and less than" << MAX << endl;
	}
	cout << "Please input the elements one by one:" << endl;
	for(i=1;i<=n;i++)
		cin >> R[i];
	cout << "The sequence you input is:" ;
	for(i=1;i<=n;i++)
		cout << "   " << R[i];

	Insert_Sort(n);

	cout << endl;
	cout << "The sequence after insert_sort is:" ;
	for(i=1;i<=n;i++)
		cout << "   " << R[i];
	cout << endl;
	return; 
}