#include <stdio.h>
#define N 500000
#define MAX 2000000000
 
void merge(int[], int, int, int);
void mergeSort(int[], int, int);
 
int L[(N/2)+2],R[(N/2)+2];
int count;
 
 
int main(){
 
  int i,n,A[N];
  cnt = 0;
 
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
 
  mergeSort(A,0,n);
 
  for(i=0;i<n;i++){
    printf("%d",A[i]);
    if(i==n-1){
      printf("\n");
      break;
    }
    printf(" ");
  }
 
  printf("%d\n",count);
 
  return 0;
}
 
 
void merge(int A[], int left, int mid, int right){
  int n1,n2,i,j,k;
   
  n1 = mid - left;
  n2 = right - mid;
   
  for(i = 0; i <= n1; i++)
    L[i] = A[left+i];
  for(i = 0; i<= n2; i++)
    R[i] = A[mid+i];
 
   L[n1] = MAX;
   R[n2] = MAX;
 
    i = 0;
    j = 0;
    for(k = left;k < right; k++){
      count++;
      if(L[i] <= R[j]){
    A[k] = L[i];
    i = i + 1;
      }
      else{
    A[k] = R[j];
    j = j + 1;
      }
    }
 