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

void mergeSort(int,int,int);
void merge(int,int,int,int);
int left, right,count;
int R[N/2],L[N/2];

int main(){
  int n,i,j,S[N];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",S[i]);
  }
  left = 0;
  right = n;
  mergeSort(S,left,right);
  for(i=0;i<n;i++){
    printf("%d ",S[i]);
  }

  printf("%d",count);
    return 0;
  }

void merge(int S[],int left,int mid,int right){
  int n1,n2,i,j,k,L[N],R[N];
  n1 = mid - left;
  n2 = right - mid;
for(i=0;i<n1;i++){
  L[i] = S[left+i];
 }
for(j=0;j<n2;j++){
  R[j] = S[mid+j];
 }

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

for (k=left;k<right-1;k++){
  count++;
  if (L[i] <= R[j]){
      S[k] = L[i];
      i = i + 1;
    }
    else{
      S[k] = R[j];
      j = j + 1;
    }
 }

}
void mergeSort(int S[], int left,int right){
  int mid;
  if (left+1 < right){
          mid = (left + right)/2;
          mergeSort(S, left, mid);
          mergeSort(S, mid, right);
          merge(S, left, mid, right);

        }
}

