////////////////////////////////////////
//ALDS1_5_A:   Exhaustive Search
//
//?????°??¢??°
//http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2530175#2
////////////////////////////////////////

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <unordered_map> //???????????\??¢??°

using namespace std;

//???????????°??????TEST????????????????????¬???????????????????????????????????¢????????????
//#define TEST //*******************************************************************************************************************************************

//?????????????????¨??§?????\????????????????????????????????°?????????????¨???????????????????dout???????????????????????§???????????¬??????????????????????????????????????????
//??????????????????????????????????????????????????????????§?CPU???????£??????????????????§???TLE?????????????????????????????????????????§????????¨???
#ifdef TEST
#define dout cout
#else
stringstream dummy; //???????????°??????dout?????????????????????????????????
#define dout dummy.str(""); dummy.clear(stringstream::goodbit); dummy //dummy?????????????????????????????????????????¨?????¢?????¢???????????????
//???????????¨??????????????????goodbit?????????????????????????????¨???????????´????????????????????????????????¨?????°?????????????????§???????????????????????????????????? http://d.hatena.ne.jp/linden/20060427/p1
#endif


#define disp(A) dout << #A << " = " << (A) << endl
#define disP(A) dout << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)

#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl


////////////////////////////////////////
//ALDS1_5_B:   Merge Sort
//
//??????????????????
//
////////////////////////////////////////

const int INF = 2e9-1;

int cnt = 0;

void merge(int *a, int left, int mid, int right) {
    
//    dout << "merge(" << left << ", " << mid << ", " << right <<")" << endl;
    
    int n1 = mid - left;
    int n2 = right - mid;
    
    int L[n1+1], R[n2+1];
    
    rep(i,0,n1) {
        L[i] = a[left + i];
    }
    L[n1] = INF;
    rep(i,0,n2) {
        R[i] = a[mid + i];
    }
    R[n2] = INF;
    
//    dispAll(L, n1+1);
//    dispAll(R, n2+1);
    
    int i = 0, j = 0;
    
    rep(k, left, right) {
        cnt++;
        
        if( L[i] <= R[j] ) {
            a[k] = L[i];
            i++;
        } else {
            a[k] = R[j];
            j++;
        }
    }

    return;
}


void mergeSort(int *a, int left, int right) {

    if(left+1  !=  right) {
        int mid = (left + right) / 2;
        
        mergeSort(a, left, mid);
        mergeSort(a, mid, right);
        
        merge(a, left, mid, right);
        
    }
    
    return;
}


int main(void) {
    int N;
    cin >> N;
    
    int a[N];
    rep(i,0,N) {
        cin >> a[i];
    }
    
//    dispAll(a, N);
    
    mergeSort(a, 0, N);
    
    
//    dispAll(a, N);
    
    rep(i,0,N) {
        cout << (i==0 ? "" : " ") << a[i];
    }
    cout << endl;
    
    cout << cnt << endl;
    
    return 0;
}

Measured memory_bytes: 6884