import java.util.*;

public class Binarysort {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] a = new int[n];
        out(a);
        sort(a);
        out(a);
    }
    public static void sort(int[] a) {
        Scanner scan = new Scanner(System.in);
        for (int i = 0; i < a.length; i++) {
            int x = scan.nextInt();
            System.out.println(x+"x");
            int l = 0;
            int r = a.length;
            int m = (l + r) / 2;
            boolean z = false;

            while (z != true) {
                if(a[0]==0){
                    a[0]=x;
                    z=true;
                }else if (a[m] >= x && a[m - 1] <= x) {
                    for (int k = a.length - 2; k > m; k--) {
                        a[k + 1] = a[k];
                    }
                    a[m] = m;
                    z = true;
                } else if (a[m] > x) {
                    r = m;
                    m = (l + r) / 2;
                } else if (a[m] < x) {
                    l = m;
                    m = (l + r) / 2;
                }
            }
        }
    }

    public static void out(int[] a) {
        System.out.println();
        for (int val : a) {
            System.out.print(val+ "  ");
        }
    }


}