public static void main(String[] args){
		
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		Node h = null;
		Node curr = h;
		while(n-->0){
			if(h==null){
				h = new Node(in.nextInt());
				curr = h;
			} else {
				curr.next = new Node(in.nextInt());
				curr = curr.next;
			}
		}
		printList(h);
		
		printList(mergeSort(h));
	}