#include <stdio.h>
#include <limits.h>

void merge(int a[],int left,int mid,int right,int ans)
{
 int i,j,k,l[250000],r[250000],n1,n2;

 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]=INT_MAX;
 r[n2]=INT_MAX;
 i=0;
 j=0;

 for(k=left;k<right;k++){
  ans++;
  if(l[i]<=r[j]{
   a[k]=l[i];
   i++;
  }else{
   a[k]=r[j];
   j++;
  }
 }
}

void mergeSort(int a[],int left,int right,int ans)
{
 int mid;

 if(left+1<right){
  mid=(left+right)/2;
  mergeSort(a,left,mid,ans);
  mergeSort(a,mid,right,ans);
  merge(a,left,mid,right,ans);
 }
}

int main(void)
{
 int i,n,ans=0,a[500000];

 scanf("%d",&n);
 for(i=0;i<n;i++){
  scanf("%d",&a[i]);
}

 mergeSort(a,0,n,ans);

 for(i=0;i<n-1;i++){
  printf("%d ",a[i]);
 }
 printf("%d\n",a[n-1]);
 printf("%d\n",ans);

 return 0;
}