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