#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 BInsertSort(SqList &L) {

     double start_time, finish_time, cord_time;

     start_time = clock();

     int i, j, low, high, m;

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

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

         low = ;

         high = i - ;

         while (low <= high) {

             m = (low + high) /;

             if (L.r[].key < L.r[m].key)

                 high = m - ;

             else

                 low = m + ;

         }

         for (j = i - ; j >= high + ; --j) {

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

         }

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

     }

     finish_time = clock();

     cord_time = (double)(finish_time - start_time) ;

     printf("BInsertSort 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);

     BInsertSort(L);

     OutPut(L);

     return ;

 }