Problem Statement:
Given an array A of integers, you're to calculate the number of inversions in this array. Number of inversions is the number of pairs (i,j) of array indices with i<j and A[i] > A[j]
Input Format:
The first line will be an integer T, the number of test cases. Then T test cases follow
every test case consists of two lines. The first line in N, the number of array elements. The second line contains the array elements themselves.
You can guarantee that T <= 100, N <= 100,000 , and all array elements are between 1 and 1,000,000,000
Output Format:
For every test case, you're to print one integer: the number of inversions, followed by endline.
Sample Input:
3
4
1 2 3 4
2
2 1
4
3 2 1 4
Sample Output:
0
1
3
Added by:

multisystem

Added at:

20150227 19:37:46 UTC

Time Limit:

3 seconds

Partial score:

Yes
