INVERSION COUNT

INVERSION COUNT (6256)


Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.

Input

The first line contains t, the number of testcases followed by a blank space. Each of the t tests start with a number n (n <= 200000). Then n + 1 lines follow. In the ith line a number A[i - 1] is given (A[i - 1] <= 10^7). The (n + 1)th line is a blank space.

Output

For every test output one line giving the number of inversions of A.

Example

Input:

2

3
3
1
2

5
2
3
8
6
1


Output: 

2
5

SOLUTION----


#include
void mergesort(int i,int j);
void merge(int i,int j);
long long a[200009],b[200009];
long long c;
int main()
{
        int t,n,i;
        scanf("%d",&t);
        printf("\n");
        while(t--) {
                scanf("%d",&n);
                for(i=0;i
                scanf("%lld",&a[i]);
                c=0;
                mergesort(0,n-1);
                printf("%lld\n",c);
                printf("\n");
                }
        return 0;       
}

void mergesort(int i,int j)
{
        if(i>=j) 
                return;
        else {
                int mid=(i+j)/2;
                mergesort(i,mid);
                mergesort(mid+1,j);
                merge(i,j);
                }
        return;
}

void merge(int i,int j)
{
        int mid=(i+j)/2,k=i;
        int l,r;
        l=i;r=mid+1;
        while(l<=mid && r<=j) {
                if(a[l]
                        b[k++]=a[l++];
                else {
                        c=c+mid-l+1;
                        b[k++]=a[r++];
                        }
                }
        if(l>mid)
                while(r<=j)
                        b[k++]=a[r++];
        else if(r>j)
                while(l<=mid)
                        b[k++]=a[l++];
        for(l=i;l<=j;l++)
                a[l]=b[l];
}