#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 500000

int n, S[MAX];
void mergesort(int *, int, int, int);
void merge(int *, int, int, int, int);

int main(){
  int i;
  scanf("%d",&n);
  for(i = 0; i < n; i++)scanf("%d",&S[i]);
  mergesort(S, n, 0, n);
  return 0;
}

void mergesort(int S[], int n, int L, int R){
  int M;
  if(L + 1 < R){
    M = (L + R) / 2;
    mergesort(S, n, L, M);
    mergesort(S, n, M, R);
    merge(S, n, L, M, R);
  }
}

void merge(int S[], int n, int L, int M, int R){
  int n1, n2, count;
  int i = 0, j = 0, k;
  int S1[MAX], S2[MAX], S3[MAX];
  n1 = M - L;
  n2 = R - M;
  for(i = 0; i < n1; i++)S1[i] = S[L + i];
  for(i = 0; i < n2; i++)S2[i] = S[M + i];
  S1[n1] = S2[n2] = 1000000;
  for(k = L; k < R; k++){
    count++;
    if(S1[i] <= S2[j]){
      S3[k] = S1[i];
      i++;
    }
    else{
      S3[k] = S2[j];
      j++;
    }
  }
  for(i = 0; i < n; i++){
    printf("%d",S3[i]);
    if(i < n - 1)printf(" ");
  }
  printf("\n");
  printf("%d\n",count);
}

