#include <stdio.h>
#include <stdlib.h>

#define NMAX 500000

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

int main (void)
{
  int n,s[NMAX],left,i,count;

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

  count = mergeSort(&s[0],0,n);

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

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

  return 0;
}

int merge (int *s,int left,int mid,int right)
{
  int n1,n2,*l,*r;
  int i,j,k;

  n1 = mid - left;
  n2 = right - mid;

  l = malloc (n1 * sizeof(int));
  r = malloc (n2 * sizeof(int));

  for (i = 0 ; i < n1 ; i++)
    l[i] = s[left + i];
  for (i = 0 ; i < n2 ; i++)
    r[i] = s[mid + i];
  //l[n1] = NULL;
  //r[n2] = NULL;

  i = 0;
  j = 0;

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

  free (l);
  free (r);

  return n1+n2;

}

int mergeSort (int *s,int left,int right)
{
  int mid,count = 0,sum = 0,sum1 = 0,sum2 = 0,i;

  if (left + 1 < right){
    mid = (left + right) / 2;
    sum1 = mergeSort (&s[0],left,mid);
    sum2 = mergeSort (&s[0],mid,right);
    count = merge (&s[0],left,mid,right);
/*
    for (i = 0 ; i < 10 ; i++)
      printf ("%d ",s[i]);
    printf ("\n");
*/
    sum = sum + sum1 + sum2 + count;
  }

  return sum;
}