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
akt_1998: 2017-04-10 19:42:03

Merge Sort->"ACIN1GO"

babur: 2017-04-05 20:10:49

Segment Tree+Merge Sort AC in 1 go :)

the_novice96: 2017-04-05 14:12:46

If BST implementation gets AC, then the test cases are weak because the running time for BST is O(nh), which is O(n^2) in worst case. Basically it should fail if the sequence is sorted.

amandal799: 2017-03-23 18:42:59

solved using binary search tree..AC in one go

rohit9934: 2017-03-15 16:36:06

For Those who are looking for hints.
Well Fenwick tree has a property of counting inversions in an array. Did a lot of work improving time complexity.Great problem. You just have to take care of duplicate elements.AC

jeelapamy: 2017-03-09 10:39:55

ha ha long long

anaar_13: 2017-03-03 16:20:51

too weak tests!!!!
I got the AC using a vector and inserting elements in their true positions and asking if there was any element bigger than this before this one was added...
it should be TLE but it is AC!

Last edit: 2017-03-03 16:22:05
shreeshiv: 2017-02-20 10:13:59

What is WA and AC??

nilabja16180: 2017-02-13 13:47:11

A great BIT problem

fane_faiz: 2017-02-09 10:21:48

Don't forget to use long long, caused me 2 WA.


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