public static void main(String[] args) throws IOException {
		BufferedReader in  = new BufferedReader(new InputStreamReader(System.in));
		int length = Integer.parseInt(in.readLine());
		String[] strArray = in.readLine().split(" ");
		int[] array1 = new int[length];
		int[] array2 = new int[length];
		for (int i = 0; i < strArray.length; i++) {
			array1[i] = Integer.parseInt(strArray[i]);
			array2[i] = Integer.parseInt(strArray[i]);
		}
		
		quickSort(array1);
		insertionSort(array2);
		System.out.println(qSwaps);
		System.out.println(iSwaps);
		System.out.println(iSwaps - qSwaps);
		for (int i = 0; i < array1.length; i++) {
			System.out.print(array1[i] + " ");
		}
		System.out.println();
		for (int i = 0; i < array2.length; i++) {
			System.out.print(array2[i] + " ");
		}
		System.out.println();

	}