Submit Best Submissions All Submissions

367. Count Inversions

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: 2015-02-27 19:37:46 UTC
Time Limit: 3 seconds
Partial score: Yes