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
natsu: 2013-04-15 16:21:46

Thanks a lot guys.Its true .got AC after taking long long int for the no. of inversions

Yashodhan S. Katte: 2013-04-15 16:21:46

@Rishabh use printf instead of cout and see.

Haidar Abboud: 2013-04-15 16:21:46

No need for merge sort - you can just view the problem as a standard BIT exercise :P

Rishabh Baid: 2013-04-15 16:21:46

would O(n log n) get accepted ? I tried using merge sort but got TLE.

StupidGuy: 2013-04-15 16:21:46

Use long long int to count inversions.

spock: 2013-04-15 16:21:46

wohooo..just changed the number of inversions to long long and got accepted.. :)

Last edit: 2012-07-01 06:01:53
data: 2013-04-15 16:21:46

@Anup use return 0

krishna_0507: 2013-04-15 16:21:46

what is this runtime error(NZEC)???m using merge sort correctly then y is it showing me then !!!!!i hv implemaented mah code code in c and used int main and returned 0 also.....then also it is showing me that error.....can anyone help me ???? thanks in advance....

I_AM: 2013-04-15 16:21:46

Thanks معاذ for your hint. Not taking long long cost me also many wrong answers. Others beware!

Aradhya: 2013-04-15 16:21:46

did it by merge sort and some hit and trail :D


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