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

 
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex ,int count)
{
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1)
    {
        if(sourceArr[i] > sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
        count ++;
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];count++;
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];count++;
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];count++;
}

void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex, int count)
{
    int midIndex;
    if(startIndex < endIndex)
    {
        midIndex = (startIndex + endIndex) / 2;
        MergeSort(sourceArr, tempArr, startIndex, midIndex, count);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex, count);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex, count);
    }
}
int main(int argc, char** argv) {
    int count=0;
    int n;
    int i;
    int S[500000];
    scanf("%d", &n);
    for(i=0; i<n; i++){
        scanf("%d", &S[i]);
    }
    int B[n];
    MergeSort(S, B, 0, n, count);
    for(i=0;i<n;i++){
        printf("%d ", S[i]);
    }
    printf("%d\n", count);
    return 0;
}
