//Inversion.cpp
//Finding the number of inversions in an array using merge sort
//Let A[1...n] be an array of n distinct numbers. If i<j and A[i]>A[j],
//then teh pair (i,j) is called an inversion of A
//This code doesn't work

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define MAX_INT 100000
int me;
using namespace std;
void Merge(int A[], int p, int q, int r)
{
    int n1=q-p+1;
    int n2=r-q;     
    int *L=new int[n1+1];
    int *R=new int[n2+1];
    for(int i=0;i<n1;i++)
            L[i]=A[p+i-1];
    for(int j=0;j<n2;j++)
            R[j]=A[q+j];

    L[n1]=MAX_INT;
    R[n2]=MAX_INT;
    int i=0;
    int j=0;
    for(int k=p-1;k<r;k++)
    {
            if(L[i]<=R[j])
            {
                A[k]=L[i];
                i=i+1; 
                me++;             
            }        
            else
            {
                A[k]=R[j];
                j=j+1;  
                  
            }
    }
 
}
////////////////////////////////////////////
void MergeSort(int A[], int p, int r)
{
    if(p<r)
    {
          int q=(p+r)/2; 
          MergeSort(A,p,q);
          MergeSort(A,q+1,r);
          Merge(A,p,q,r);    
    }
}
///////////////////////////////////////////////
int main()
{
   
   int n;
   cin>>n;
  
   int *A=new int[n];
   for(int i=0;i<n;i++)
           cin>>A[i];
   MergeSort(A,1,n);
   for(int i=0;i<n;i++)
           cout<<A[i]<<"\t";
   cout<<endl<<me;
   getchar();
   getchar();
   return 0;
}