치우친 정렬

농부 John에게는 $2^N$마리($1 \le N \le 10$)의 소가 있고, 각 소의 옆구리에는 $1 \dots 2^N$ 범위의 서로 다른 정수 번호가 하나씩 칠해져 있습니다. 소들은 임의의 순서로 한 줄로 서 있으며, 줄의 첫 번째 소는 $\mathrm{cow}_1$, 두 번째 소는 $\mathrm{cow}_2$, 이런 식으로 이어집니다.

John은 다음 재귀 절차로 소들의 순서를 바꿉니다.

1. 현재 줄에 소가 두 마리 이상 있으면, 길이가 같은 두 개의 절반으로 나눕니다. 먼저 왼쪽 절반에 이 절차를 그대로 적용하고, 그다음 오른쪽 절반에 적용합니다.
2. 처리된 두 절반을 각각 $2^N$진법으로 쓴, 자릿수가 같은 두 수로 봅니다(소 한 마리가 한 자리이고, 가장 왼쪽이 최상위 자리). 두 번째(오른쪽) 수가 첫 번째(왼쪽) 수보다 작으면 두 절반을 통째로 맞바꿉니다. 즉 왼쪽 절반의 각 위치에 있는 소가 오른쪽 절반의 같은 위치에 있는 소와 자리를 교환합니다.

모든 번호가 서로 다르므로 두 절반이 같을 수는 없고, 따라서 이 비교는 항상 대소가 정해집니다.

길이가 $k$인 두 절반을 맞바꿀 때마다 관련된 $2k$마리 소가 모두 정확히 $k$칸씩 이동하므로, 그 교환은 누적 이동 거리에 $2k^2$을 더합니다.

처음 줄에 이 절차를 실행한 뒤, 모든 소가 이동한 총 거리와 최종 줄 순서를 출력하세요.

예로 $2^3 = 8$마리 소가 다음과 같이 서 있다고 합시다.

8 5 2 3 4 7 1 6

먼저 John은 각 절반을 따로 정리합니다.

8 5 2 3 | 4 7 1 6

각 절반에도 아직 소가 두 마리 이상 있으므로 다시 나눕니다. 왼쪽 절반부터 시작하면

8 5 | 2 3

한 번 더 나누면

8 | 5      그리고      2 | 3

이 되고, 각각 규칙 2로 처리하여 최종적으로

5 | 8      그리고      2 | 3   (그대로)

가 됩니다. 8 5를 5 8로 바꾸면 두 소가 각각 한 칸씩 이동하므로 총 거리는 $2$가 됩니다. 2 3은 이미 정렬되어 있으므로 총 거리는 $2$로 유지됩니다. 이제 왼쪽 그룹은 다음과 같습니다.

5 8 | 2 3

5 8과 2 3에 규칙 2를 적용하면, 2가 5보다 앞서므로 두 쌍을 맞바꿉니다.

2 3 5 8

이 네 마리 소가 각각 두 칸씩 이동해 $8$이 더해지므로 총 거리는 $10$이 됩니다.

이제 오른쪽 그룹 4 7 | 1 6은 4 7과 1 6으로 나뉘며 둘 다 이미 정렬되어 있습니다. 둘을 비교하면 1이 4보다 앞서므로 맞바꿉니다.

1 6 4 7

여기서 $8$이 더 더해져 총 거리는 $18$이 됩니다.

이제 줄은 다음과 같으며, 네 마리씩인 두 그룹에 규칙 2를 마지막으로 적용할 차례입니다.

2 3 5 8 | 1 6 4 7

1이 2보다 앞서므로 두 절반을 맞바꿉니다.

1 6 4 7 2 3 5 8

여덟 마리 소가 각각 네 칸씩 이동해 $32$가 더해지므로 총 거리는 $50$이 됩니다.

따라서 답은 거리 $50$과 최종 줄 1 6 4 7 2 3 5 8입니다.

• 첫째 줄: 정수 $N$ 하나.
• 둘째 줄부터 $2^N + 1$째 줄까지: $i + 1$째 줄에는 $\mathrm{cow}_i$의 번호인 정수 하나가 있습니다.

• 첫째 줄: 모든 소가 이동한 총 거리인 정수 하나.
• 둘째 줄부터 $2^N + 1$째 줄까지: $i + 1$째 줄에는 최종 줄에서 $i$번째 소를 나타내는 정수 하나를 출력합니다.