‘‘‘

include[HTML_REMOVED]

using namespace std;

int a[1000001],n;
int b[1000001],tmp[1000001];

void QuickSort(int q[], int l, int r)
{
if (l >= r) return;

int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
    do i ++ ; while (q[i] < x);
    do j -- ; while (q[j] > x);
    if (i < j) swap(q[i], q[j]);
}
QuickSort(q, l, j), QuickSort(q, j + 1, r);

}

int ans;
void MergeSort(int q[],int l,int r)
{
if(l==r)return;
int i=l,mid=(l+r)/2,j=mid+1,k=l;

MergeSort(q,l,mid);
MergeSort(q,mid+1,r);

while(i<=mid&&j<=r)
{
    if(q[i]<=q[j]){
        b[k++]=q[i++];
    }
    else{
        ans=ans+j-k;
        b[k++]=q[j++];
    }
}
while(i<=mid) b[k++]=q[i++];
while(j<=r) b[k++]=q[j++];
for(int i=l;i<=r;i++)
    q[i]=b[i];

}

void MergeFindSort( int a[] , int n )
{
int low , high , mid ;
int temp ;
for ( int i=1 ; i[HTML_REMOVED] temp )
high = mid - 1 ;
else
low = mid + 1 ;
}
for ( int j = i - 1 ; j > high ; j– )
a[j+1] = a[j] ;
a [high+1] = temp ;
}
}

void ShellSort(int ar[],int l)
{
int d=l/2;
int i,j,temp;
while(d>=1)
{
for(int i=d;i[HTML_REMOVED]=0 && ar[j]>temp)
{
ar[j+d]=ar[i];
j-=d;
}
}
d/=2;
}
}

void CountingSort(int q[],int n)
{
for(int i=0;i[HTML_REMOVED]=0;i–)
if(tmp[i]!=0)
for(int j=0;j<tmp[i];j++)
q[n–]=tmp[i];
}

/***********/
int getMax(int a[], int n)
{
int i, max;
max = a[0];
for (i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
void countSort(int a[], int n, int exp)
{
int output[n];
int i, buckets[10] = {0};

for (i = 0; i < n; i++)
    buckets[ (a[i]/exp)%10 ]++;

for (i = 1; i < 10; i++)
    buckets[i] += buckets[i - 1];

for (i = n - 1; i >= 0; i--)
{
    output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
    buckets[ (a[i]/exp)%10 ]--;
}
for (i = 0; i < n; i++)
    a[i] = output[i];

}
void radixSort(int a[], int n)
{
int exp;
int max = getMax(a, n);
for (exp = 1; max/exp > 0; exp = 10)
countSort(a, n, exp);
}
/**********/

int main()
{
cin>>n;
for(int i=0;i[HTML_REMOVED]>a[i];

radixSort(a,n);
CountingSort(a,n);
ShellSort(a,n);
MergeFindSort(a,n);

MergeSort(a,0,n-1);
cout<<endl<<ans<<endl;
stable_sort(a,a+n);

QuickSort(a,0,n-1);
sort(a,a+n)

for(int i=0;i<n;i++)
    cout<<a[i]<<" ";
return 0;

}