#include <bits/stdc++.h>

 using namespace std;

 #define MAXSIZE 200000

 typedef int KeyType;

 typedef struct {

     KeyType key;

 }RedType;

 typedef struct {

     RedType r[MAXSIZE + ];

     int length;

 }SqList;

 int Random(int start, int end){

     int dis = end - start;

     return rand() % dis + start;

 }

 void InsertSort(SqList &L) {

     double start_time, finish_time, cord_time;

     start_time = clock();

     int i, j;

     for (i = ; i <= L.length; ++i) {

         if (L.r[i].key < L.r[i-].key) {

             L.r[] = L.r[i];

             L.r[i] = L.r[i-];

             for (j = i-; L.r[].key < L.r[j].key; --j) {

                 L.r[j+] = L.r[j];

             }

             L.r[j+] = L.r[];

         }

     }

     finish_time = clock();

     cord_time = (double)(finish_time - start_time) ;

     printf("InsertSort time=%f ms\n", cord_time);

 }

 void InPut(SqList &L) {

     int i;

     srand((unsigned)time(NULL));

     cin >> L.length;

     for (i = ; i <= L.length; ++i) {

         // cin >> L.r[i].key;

         L.r[i].key = Random(, );

     }

 }

 void OutPut(SqList &L) {

     int i;

     for (i = ; i <= L.length; ++i) {

         cout << L.r[i].key << " ";

     }

 }

 int main() {

     SqList L;

     // L.r = new RedType [MAXSIZE+1];

     InPut(L);

     InsertSort(L);

     OutPut(L);

     return ;

 }