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

#define MAX_DATA_NUM      500000
#define HALF_MAX_DATA_NUM (MAX_DATA_NUM/2)

static void Merge_Void(int *pSortBuff, int LeftNum, int RightNum );

int main(void)
{
    int data_num;			/* Data Num */
	int db;					/* Data Block */
	int cn = 2;				/* Compare Num */
	int mn = 0;				/* merge num */
	int half = 1;			/* Compare Half Num */
    int *pSortBuff;
	int remainder;          /* amari */
	int position;
	int loop;
    
    pSortBuff = (int *)malloc(sizeof(int) * MAX_DATA_NUM);
    /* get "Data Block Num" */
    scanf("%d", &db);
     
    /* get Name & time */
    while((scanf("%d", &(pSortBuff[data_num])) != EOF) && data_num < MAX_DATA_NUM)
    {
        data_num++;
    }
    
	
    /* get Data Num equal process num */
    if( data_num == db )
    {
         while(db > 1)
        {
        	position = 0;
    		db /= cn;
		   	remainder = data_num % cn;
        	
        	for(loop=0; loop<db; loop++)
        	{
        		Merge_Void(&(pSortBuff[position]), half, half);
        		position += cn;
        		mn++;
        	}
        	
        	if(remainder > half)
        	{
        		Merge_Void(&(pSortBuff[position]), half, (remainder - half));
        		mn++;
        	}
        	
        	half = cn;
        	cn *= 2; /* double compare num */
        }
    	
    	remainder = data_num - half;
    	if(remainder > 0)
    	{
    		Merge_Void(&(pSortBuff[0]), half, remainder);
        	mn++;
    	}
    	else
    	{
    		/* Nothing */
    	}
    }
    else
    {
        /* error input */
    }
	
	for(loop=0; loop<data_num-1; loop++)
	{
		printf("%d ", pSortBuff[loop]);
	}
	printf("%d\n%d", pSortBuff[data_num-1], mn);
	
	free(pSortBuff);
    return 0;
}

void Merge_Void(int *pSortBuff, int LeftNum, int RightNum )
{
    int *pLeftBuff;
    int *pRightBuff;
	int loop;
	int ln = 0;
	int rn = 0;
	
	
    pLeftBuff = (int *)malloc(sizeof(int) * LeftNum);
    pRightBuff = (int *)malloc(sizeof(int) * RightNum);
	
	/* Input Left Buffer */
	for( loop=0; loop<LeftNum; loop++ )
	{
		pLeftBuff[loop] = pSortBuff[loop];
	}
	
	/* Input Right Buffer */
	for( loop=0; loop<RightNum; loop++ )
	{
		pRightBuff[loop] = pSortBuff[LeftNum + loop];
	}
	
	/* merge */
	for( loop=0; loop<(LeftNum + RightNum); loop++ )
	{
		if(ln == LeftNum)
		{
			pSortBuff[loop] = pRightBuff[rn];
			rn++;
		}
		else if(rn == RightNum)
		{
			pSortBuff[loop] = pLeftBuff[rn];
			ln++;
		}
		else if(pRightBuff[rn] > pLeftBuff[rn])
		{
			pSortBuff[loop] = pRightBuff[rn];
			rn++;
		}
		else
		{
			pSortBuff[loop] = pLeftBuff[rn];
			ln++;
		}
	}
	
	free(pLeftBuff);
	free(pRightBuff);
}