#include <stdio.h>
#define n 500000
#define N 1000000000

int L[(n/2) + 2],R[(n/2) + 2];
int c;

void Merge(int A[], int m, int left, int mid, int right){
  int i,j,k,n1,n2;
  n1 = mid-left;
  n2 = right-mid;

  for(i=0 ; i<n1 ; i++){
    L[i] = A[left+1];
  }

  for(i=0 ; i<n2 ; i++){
    R[i] = A[mid+1];
  }

  L[n1] = R[n2] = N;
  i=0;
  j=0;

  for(k=left ; k<right ; k++){
    c++;
    if(L[i] <= R[j]){
      A[k] = L[i++];
    }
    else{
      A[k] = R[j++];
    }
  }
}

void MergeSort(int A[], int m, int left, int right){
  int mid;
  if((left+1)<right){
    mid = (left + right) / 2;
    MergeSort(A, n, left, mid);
    MergeSort(A, n, mid, right);
    Merge(A, n, left, mid, right);
  }
}

int main(){
  int x,i,A[n];

  scanf("%d",&x);

  c=0;

  for(i=0; i<x; i++){
    scanf("%d",&A[i]);
  }
  MergeSort(A, x, 0, x);
  for(i=0; i<x-1; i++){
    printf("%d ",A[i]);
  }
  printf("%d\n",A[x-1]);
  printf("%d\n",c);

  return 0;
}

