#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
const int N = 500010;
int n,cnt;
int a[N]; int L[N>>1]; int R[N>>1];
void merge(int left,int mid,int right)
{
	int x=mid-left;
	int y=right-mid;
	for(int i=0;i<x;i++)
	L[i]=a[i+left];
	for(int i=0;i<y;i++)
	R[i]=a[mid+i];
	L[x]=R[y]=INF;
	int i=0,j=0;
	for(int k=left;k<right;k++)
	{
		cnt++;
		if(L[i]<=R[j])
		{
			a[k]=L[i];
			i++;
		}
		else
		{
			a[k]=R[j];
			j++;
		}
	}
	
}
void sort(int left ,int right)
{
	if(left<right-1) 
	{
		int mid=(left+right)>>1;
		sort(left,mid);
		sort(mid,right);
		merge(left,mid,right);
	}	
}
void print()
{
    for(int i = 0; i < n; i ++)
    {
        if(i == n-1) printf("%d\n",a[i]);
        else printf("%d ",a[i]);
    }
    printf("%d\n",cnt);
    return ;
}
int main()
{
    cnt = 0;
    scanf("%d",&n);
    for(int i = 0; i < n; i ++)
        scanf("%d",&a[i]);
    sort(0,n);
    print();
    return 0;
}