
#include <stdio.h>

#define MAX_DATA 10

int temp[MAX_DATA],num1=0;
int x[500000];/* ????°???§???????????¨????????????????????????????????? */

int MergeSort(int x[ ], int left, int right);
int main(void);

  /* ?????? x[ ] ??? left ?????? right ???????´??????????????????????????????? */
int MergeSort(int x[ ], int left, int right)
{
    int mid, i, j, k;
	
    if (left >= right)              /* ?????????????´?????????¨????????? */
        return;                     /* ?????????????????§?????? */

                                    /* ????????§??????????????????????????? */
    mid = (left + right) / 2;       /* ?????????????????? */
    MergeSort(x, left, mid);        /* ???????????°???????????? */
    MergeSort(x, mid + 1, right);   /* ???????????°???????????? */

      /* x[left] ?????? x[mid] ???????\??????????????????? */
    for (i = left; i <= mid; i++)
        temp[i] = x[i];

      /* x[mid + 1] ?????? x[right] ????????????????????? */
    for (i = mid + 1, j = right; i <= right; i++, j--)
        temp[i] = x[j];

    i = left;         /* i ??¨j ???????\????????????????????????? */
    j = right;        /* k ????????????????´??????????????????? */

    for (k = left; k <= right; k++){
      num1++;/* ?°??????????????????????????????? */
      if (temp[i] <= temp[j]) x[k] = temp[i++];
      else x[k] = temp[j--];
    }
    return 0;
}

int main(void)
{
  int i,n;
      /* ??????????????????????????? */

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

    MergeSort(x, 0, MAX_DATA - 1);

      /* ?????????????????????????????¨??? */
    //    printf("????????????\n");
    for (i = 0; i < n; i++){
        printf("%d", x[i]);
	if(i<n)printf(" ");
	else break;
    }
    printf("\n%d\n",num1);
    return 0;
}