## INVCNT - Inversion Count

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```

hide comments
 naive_coder: 2013-04-15 16:21:46 please have a look at the range that count will have to store :)got AC after i just fixed it Last edit: 2011-08-23 14:15:40 Dunno: 2013-04-15 16:21:46 sometimes it happens. coder: 2013-04-15 16:21:46 well well, my soln gets accepted in 0k.. lolz.. cant understand the logic how spoj calculates memory consumed. :P Chetan Gupta: 2013-04-15 16:21:46 @Boopathi: for first test case: 3 3 1 2 the first line contains the number of elements in the array. so 3 is the number of elements and 3,1,2 are elements. Boopathi Rajaa: 2013-04-15 16:21:46 how is it that there are only 2 inversions in first case ??? 0,2 ; 0,3 ; 1,2 ; 1,3 => 4 inv Edit : The 2 inversions are (3,1) and (3,2). Read the problem statement carefully. Last edit: 2011-05-26 04:42:45

 Added by: Paranoid Android Date: 2010-03-06 Time limit: 3.599s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: PERL6