#include<stdio.h>

#define Infty 2000000
#define Max 500000

int L[Max/2+2],R[Max/2+2];
int c=0;
void merge(int [], int, int, int, int);
void mergesort(int [],int,  int, int);
int main(){
  int n;
  int s[Max];
  int i;
  scanf("%d",&n);
  for(i=0; i < n; i++){
    scanf("%d",&s[i]);
  }

  mergesort(s,n,0,n);
  for(i=0;i < n; i++){
    if(i) printf(" ");
    printf("%d ",s[i]);
  }
  printf("\n");
  printf("%d\n",c);

  return 0;

void merge(int A[],int n, int left,int mid,int right){
    int n1,n2;
    int 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]=Infty;
   L[n2]=Infty;
    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 n, 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);
  }
}