총 이동 거리

인욱은 $2^N$ (1 <= N <= 10)개의 공을 가지고 있는데, 각 공에는 1..$2^N$ 범위의 번호가 적혀져 있으며, 공은 무작위 순서로 배열되어있다. 

첫 번째 공을 $ball_1$, 두 번째 공을 $ball_2$라 하고, 이런 식으로 계속해서 $(1 \lt= ball_i \lt= 2^N)$로 명명한다. 물론, $ball_1$에 붙여진 라벨이 1일 확률은 매우 낮다.

인욱은 공들을 정렬하기 위해 다음과 같은 알고리즘을 수행한다.

1. 만약 공이 1개 이상이면, 공들을 동일한 크기의 2개의 하위 그룹으로 나눈다. 이 알고리즘을 사용하여 첫 번째 하위 그룹을 정렬하고, 그런 다음 두 번째 하위 그룹을 정렬한다.
2. 현재의 공 세트를 동일한 길이의 $2^N$의 2개의 (아마도 엄청난 크기의) 숫자 쌍으로 정렬한다고 가정한다. 두 번째 숫자가 첫 번째 수보다 작다면, 두 번째 숫자의 모든 요소를 첫 번째 숫자의 요소로 교환한다.

인욱은 공들이 이 '정렬' 과정에서 얼마나 많이 움직였는지 알고 싶어한다.

• 공의 초기 구성이 주어진 경우, 위의 알고리즘에 따라 처리한 뒤, 다음을 출력한다:
• 모든 공이 이동한 전체 거리의 합계
• '정렬' 과정 후, 공들의 최종 구성

예를 들어, $2^3$=8 개의 공으로 구성된 배열을 생각해보자:

        8 5 2 3 4 7 1 6

먼저, 인욱은 줄에서 각 절반을 따로 정렬한다:

        8 5 2 3 | 4 7 1 6

각 절반에 공이 여러 개이므로, 인욱은 '첫 번째' 절반부터 시작하여 해당 절반을 개별적으로 정렬한다:

        8 5 | 2 3

다시 분할하면, 인욱은

        8 | 5      and        2 | 3

를 만들었고, 이는 두 번째 규칙에 따라 각각 정렬하여 최종적으로는 아래와 같이 산출 할 수 있다.:

        5 | 8      and        2 | 3 (<--unchanged)

첫 번째 하위 그룹의 정렬 과정에서 각 공이 이동하는 거리는 1이므로, total_distance_moved는 2가 된다. 두 번째 절반은 이미 정렬되어 있으므로, total_distance_moved는 2에 머무른다. 이 하위 그룹의 새로운 구성은 다음과 같다:

        5 8 | 2 3

위 하위 그룹에 대한 알고리즘의 2단계에서는, 양 쪽을 사전 순으로 비교하면 (5 8 vs. 2 3), 2가 5보다 앞에 오기 때문에, 첫 번째 절반의 두 요소를 두 번째 절반의 해당 요소와 교환하여 다음과 같이 산출한다.

        2 3 5 8

이 교환에서 4개의 공 각각이 공간 2를 총 8회 이동하므로, total_distance_moved는 10이 된다.

나머지 절반의 공들을 살펴보면, 4개의 목록을 2개의 하위그룹으로 나눈다:

        4 7 | 1 6

각 쌍 (4, 7)과 (1, 6)은 이미 정렬된 순서이다.

(4 7)을 (1 6)과 비교하면, 1이 4보다 앞에 오므로 두 하위 그룹을 교환해야 한다:

        1 6 4 7

이로 인해 총 8회 더 이동하게 되어, total_distanced_move는 18이 된다.

위의 작업 후 목록은 다음과 같이 표시된다. (두 그룹에 대해 2단계를 수행할 차례다):

        2 3 5 8 | 1 6 4 7

1이 2보다 앞에 오므로, 절반이 교환되어야 한다, 이로 인해 다음과 같은 구성이 됩니다:

        1 6 4 7 2 3 5 8

8개의 공 각각이 4 단위로 움직였으므로, 이는 총 32회의 추가로 이동한 것을 의미하며, total_distance_moved는 50이 된다

따라서, 답은 50과 1 6 4 7 2 3 5 8이다.

• 첫 번째 줄 : 하나의 정수: N
• 두 번째 줄부터 $2^N$+1번째 줄 : i+1번째 줄에는 하나의 정수: ball_i가 포함되어 있다

• 첫 번째 줄: 하나의 정수, 모든 공들에 의해 이동한 총 거리
• 두 번째 줄부터 $2^N$+1번째 줄 :  i+1번째 줄에는 하나의 정수: 최종 설정에서의 i번째 공을 포함하고 있다