/* Author: Mohamed Elshenawy
	Date: 19/6/2017
	Insertion Sort Implementation in java
*/
import java.util.Scanner;

public class InsertionSort {

	private static Scanner sc;

	public InsertionSort() {
	}

	public final void Sort(int[] arr) {
		int len = arr.length, in, out;
		for (out = 1; out < len; out++) {
			int temp = arr[out];
			in = out;
			while (in > 0 && arr[in - 1] >= temp) {
				arr[in] = arr[in - 1];
				--in;
			}
			arr[in] = temp;
		}
	}

	public static void main(String[] args) {
		sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];

		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		for (int i : a) {
			System.out.print(i + " ");
		}
		System.out.println("\n");
		InsertionSort iSort = new InsertionSort();
		iSort.Sort(a);
		for (int i : a) {
			System.out.print(i + " ");
		}
	}
}