import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    static int[] arr;
    static int[] sorted;
    static int count;

    static void merge(int[] arr, int left, int middle, int right){                        
        int index_L = left;
        int index_R = middle + 1;
        int index_N = left; 
        while(index_L <= middle && index_R<=right){
            if (arr[index_L] < arr[index_R]) {
                sorted[index_N] = arr[index_L]; 
                index_L ++;
            } else {
                sorted[index_N] = arr[index_R];
                index_R ++;
                count ++;                                                                   
                }
            // count ++;
            index_N++;        
            }

        while(index_L <= middle) {
            sorted[index_N] = arr[index_L]; 
            index_L ++;
            index_N ++;        
            // count ++;
        }

        while(index_R <= right) {
            sorted[index_N] = arr[index_R];
            index_R ++;
            index_N ++;
            // count ++;
        }   

        for (int i = left; i <= right; i++) {
            arr[i] = sorted[i];
            
        }
        
    }

    static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(arr, left, middle);
            mergeSort(arr, middle+1, right);
            merge(arr, left, middle, right);
        }
    }
    
    
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        arr = new int[n];
        sorted = new int[n]; 

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        mergeSort(arr, 0, n-1); // 시작은 0, 끝은 n (미포함)

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append(i == n - 1 ? "" : " ");
        }
        System.out.println(sb.toString());
        System.out.println(count);
    }
}