// to find the inversion count of array
#include<stdio.h>
#include<limits.h>

int count=0;

void inversion_count(long long int a[],int lo,int mid,int hi)
{
    int i,j,k,n1,n2;
    n1=mid-lo+1;
    n2=hi-mid;
    int l[100000],r[100000];
    for(i=0;i<n1;++i)
        l[i]=a[lo+i];
    for(j=0;j<n2;++j)
        r[j]=a[mid+j];
    i=j=0;
    l[n1]=INT_MAX;
    r[n2]=INT_MAX;
    for(k=lo;k<hi;++k)
    {
        if(l[i]<=r[j])
        {
            a[k]=l[i];
            ++i;
        }
        else
        {
            a[k]=r[j];
            ++j;
//            count+=mid-i+1;
        }
    }
    return;
}

void partition(long long int a[],int lo,int hi)
{
    int mid;
    if(lo<hi)
    {
        mid=(lo+hi)/2;
        partition(a,lo,mid);
        partition(a,mid+1,hi);
        inversion_count(a,lo,mid,hi);
    }
}

int main()
{
    int t,n,i;
    long long arr[200000];
    scanf("%d\n\n",&t);
    while(t--)
    {
        count=0;
        scanf("%d\n",&n);
        for(i=0;i<n;++i)
        {
            scanf("%d",&arr[i]);
        }
        partition(arr,0,n-1);
        printf("\n%d",count);
    }
    for(i=0;i<n;++i)
    {
        printf("%d\t",arr[i]);
    }
    return 0;
}