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

class Main {
    static int count;
    static int[] a;
    static int INF;

    static void merge(int left, int mid, int right) {
        int nl = mid - left;
        int nr = right - mid;

        int[] L = new int[nl+1];
        int[] R = new int[nr+1];

        for (int i=0; i<nl; i++) {
            L[i] = a[left + i];
        }

        for (int i=0; i<nr; i++) {
            R[i] = a[mid + i];
        }

        L[nl] = INF;
        R[nr] = INF;

        int l_idx = 0;
        int r_idx = 0;
        for (int i=left; i<right; i++) {
            if(L[l_idx] < R[r_idx]) {
                a[i] = L[l_idx];
                l_idx++;
            } else {
                a[i] = R[r_idx];
                r_idx ++;
                count ++;
            }
        }
    }

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

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

        merge_sort(a, 0, n); 

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