#include <stdio.h>

#define N 500000
#define S 1000000000

int merge(int *,int,int,int);
void mergeSort(int *,int,int);

int n,s[N],count=0,tmp[N],x[N];

int main()
{

  int i,x;

  scanf("%d",&n);

  for(i=0;i<n;i++){

    scanf("%d",&s[i]);

  }

  mergeSort(s,0,n-1);

  for(i=0;i<n-1;i++){

    printf("%d ",s[i]);

  }
  printf("%d\n",s[n-1]);

  printf("%d\n",count);

  return 0;

}



void mergeSort(int A[],int left,int right){

  int mid,i,j,k;

  if(left>=right) return;

    mid=(left+right)/2;

    mergeSort(A,left,mid);
    mergeSort(A,mid+1,right);

    for(i=left;i<=mid;i++){
      tmp[i]=A[i];}

    for(i=mid+1,j=right;i<=right;i++,j--){
      tmp[i]=A[j];
    }

    i=left;
    j=right;

    for(k=left;k<=right;k++){

      if(tmp[i]<=tmp[j]) A[k]=tmp[i++];
      else A[k]=tmp[j--];  

      count++;
}
}