#include <stdio.h>

#define MAXSIZE 500000
#define SENTINEL 2000000000

int c; //camparisons

void trace(int A[], int N){
    for(int i = 0; i < N; i++){
        if(i > 0) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
}

void merge(int A[], int left, int mid, int right){

    int i, j, k;

    int n1 = mid - left;
    int n2 = right -mid;

    int L[n1 + 1], R[n2 + 1];

    for(i = 0; i < n1; i++){
        L[i] = A[left + i];
    }
    for(i = 0; i < n2; i++){
        R[i] = A[mid     + i];
    }
    R[n1 + 1] = SENTINEL;
    R[n2 + 1] = SENTINEL;
    
    i = 0;
    j = 0;
    for(k = left; k < right; k++){
        if(L[i] <= R[j]){
            A[k] = L[i];
            i++;
        }else{
            A[k] = R[j];
            j++;
        }
        c++;
    }
}

void mergesort(int A[], int left, int right){
    
    int mid;
    int c; //comparisons
    
    if(left + 1 < right){
        mid = (left + right) / 2;
        mergesort(A, left, mid);
        mergesort(A, mid, right);
        merge(A, left, mid, right);
    }


}

int main(){

    int A[MAXSIZE];
    int i, N;

    scanf("%d", &N);
    for(i = 0; i < N; i++) scanf("%d", &A[i]);

    mergesort(A, 0, N);

    trace(A, N);
    printf("%d\n", c);

    return 0;
}
