#include <iostream>
#include <vector>
 
using namespace std;
 
void print1(const vector<int> &a) {
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}
 
void sort_ins(vector<int> &a) {
	for (int i = 1; i < a.size(); i++) {
		int c = a[i];
		int k = i;
 
		while (k > 0 && a[k-1] > c) {
			a[k] = a[k-1];
			k--;
		}
		a[k] = c;
	}
}
 
int main() {
	int m;
	cin >> m;
 
	vector<int> a (m, 0);
	for (int i = 0; i < a.size(); i++) {
		cin >> a[i];
	}
 
	print1(a);
 
	sort_ins(a);
 
	print1(a);
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgcHJpbnQxKGNvbnN0IHZlY3RvcjxpbnQ+ICZhKSB7Cglmb3IgKGludCBpID0gMDsgaSA8IGEuc2l6ZSgpOyBpKyspIHsKCQljb3V0IDw8IGFbaV0gPDwgIiAiOwoJfQoJY291dCA8PCBlbmRsOwp9Cgp2b2lkIHNvcnRfaW5zKHZlY3RvcjxpbnQ+ICZhKSB7Cglmb3IgKGludCBpID0gMTsgaSA8IGEuc2l6ZSgpOyBpKyspIHsKCQlpbnQgYyA9IGFbaV07CgkJaW50IGsgPSBpOwoJCQoJCXdoaWxlIChrID4gMCAmJiBhW2stMV0gPiBjKSB7CgkJCWFba10gPSBhW2stMV07CgkJCWstLTsKCQl9CgkJYVtrXSA9IGM7Cgl9Cn0KCmludCBtYWluKCkgewoJaW50IG07CgljaW4gPj4gbTsKCQoJdmVjdG9yPGludD4gYSAobSwgMCk7Cglmb3IgKGludCBpID0gMDsgaSA8IGEuc2l6ZSgpOyBpKyspIHsKCQljaW4gPj4gYVtpXTsKCX0KCQoJcHJpbnQxKGEpOwoJCglzb3J0X2lucyhhKTsKCQoJcHJpbnQxKGEpOwoJCglyZXR1cm4gMDsKfQ==

MTAKMTggLTMgMTQgNSAyNSA2OSAxMDggMzQgMjEgOTY=

10
18 -3 14 5 25 69 108 34 21 96