#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "math.h"

int *create_arr(int );
void print_arr(int *, int);
void bubble_sort(int *, int);
void insert_sort(int *, int);
int bin_search(int *, int, int);
void insert_sort_with_bin_search(int *, int);
int bin_search_for_insert_sort(int *, int , int );
int log_for_bin_search(int );

int main() {
    int n;
    scanf("%d", &n);
    int *arr = create_arr(n);
    print_arr(arr, n);
    printf("\n");
    insert_sort_with_bin_search(arr, n);
    print_arr(arr, n);
    return 0;
}

int *create_arr(int size){
    int *arr = (int *)malloc(size * sizeof(int));
    srand((unsigned int)time(0));
    for (int i = 0; i < size; ++i){
        arr[i] = rand() % size;
    }
    return arr;
}

void bubble_sort(int *arr, int size){
    int t;
    for(int i = 0; i < size - 1; ++i){
        for (int j = 0; j < size - i - 1; ++j){
            if (arr[j] < arr[j + 1]){
                t = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = t;
            }
        }
    }
}

void insert_sort(int *arr, int n){
    int t, j;
    for (int i = 1; i < n; ++i){
        t = arr[i];
        j = i - 1;
        while((j >= 0) && (arr[j] > t)){
            arr[j + 1] = arr[j];
            arr[j] = t;
            --j;
        }

    }
}

void insert_sort_with_bin_search(int *arr, int n){
    int t, j, pos;
    for (int i = 1; i < n; ++i){
        t = arr[i];
        j = i - 1;
        pos = bin_search_for_insert_sort(arr, t, j);
        while ((j >= pos) && (arr[j] >= t)){
            arr[j + 1] = arr[j];
            arr[j] = t;
            --j;
        }
    }
}


int log_for_bin_search(int n){
    if (n == pow(2, (int)log2(n))){
        return (int)log2(n);
    }
    else{
        return (int)log2(n) + 1;
    }
}


int bin_search_for_insert_sort(int *arr, int item, int n){
    int m, l = 0, r = n - 1, i = 0, ans = 0;
    if (n == 0){
        return 0;
    }
    m = (r - l) / 2;
    while (i < log_for_bin_search(n)){
        if (arr[m] == item){
            return m;
        }
        else if (arr[m] > item){
            r = m;
            m = (r - l) / 2;
        }
        else {
            l = m;
            m = ((r - l) > 1) ? ( l + (r - l) / 2) : (l + 1);
        }
        ++i;
    }
    return m > n - 1 ? n - 1 : m;
}

int bin_search(int *arr, int item, int n){
    int m, l = 0, r = n - 1, i = 0;
    while (i < (int)log2(n)){
        m = (r - l) / 2;
        if (arr[m] == item){
            return 1;
        }
        if (arr[m] > item){
            r = m;
        }
        else {
            l = m;
        }
        ++i;
    }
    return 0;
}

void print_arr(int *arr, int n){
    for (int i = 0; i < n; ++i){
        printf("%d\t", arr[i]);
    }
    printf("\n");
}