#include<stdio.h>

#define SIZE 500000
#define MERGESIZE (SIZE/2+1)
#define SENTINEL (1000000000+1)

int S[SIZE];
int L[MERGESIZE], R[MERGESIZE];

int Merge(int A[], int left, int mid, int right)
{
  int n1 = mid - left;
  int n2 = right - mid;
  int i, j, k;
  
  for(i = 0; i <= n1-1; i++){
    L[i] = A[left + i];
  }
  for(i = 0; i <= n2-1; i++){
    R[i] = A[mid + i];
  }
  L[n1] = SENTINEL;
  R[n2] = SENTINEL;

  i = 0;
  j = 0;
  for(k = left; k <= right-1; k++){
    if(L[i] <= R[j]){
		A[k] = L[i];
		i = i + 1;
	}else{
		A[k] = R[j];
		j = j + 1;
	}
  }

  return(right - left);
}

int Merge_Sort(int A[], int left, int right)
{
	int mid, c = 0;
	if(left+1 < right){
		mid = (left + right)/2;
		c += Merge_Sort(A, left, mid);
		c += Merge_Sort(A, mid, right);
		c += Merge(A, left, mid, right);
	}else{
		c = 0;
	}
	return(c);
}

int main()
{
	int n, i, c;

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

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

	return(0);
}