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
zhanbolat: 2017-01-22 17:32:14

I didn't get relation between graph theory and this problem.
Can somebody share with #graph,#shortest path solution ?

Last edit: 2017-01-22 17:33:06
muneebaadil: 2017-01-20 18:15:37

Oh damn you long long! Probably a lesson for me to be conscious with data types from now on..

scorpion_ajay: 2017-01-19 11:44:24

best for learners, learning overloaded, spent two days, came out of no hope.
Finally AC :)

gauravgb21: 2016-12-29 07:59:30

jst modify the mergesort algorithm
and thts all!!

aditya930: 2016-12-27 23:53:59

use enhanced merge sort and long long to get AC !!

supercool2204: 2016-12-27 20:40:05

Last edit: 2017-06-02 15:15:34
aditya9125: 2016-12-25 21:12:12

Use long long for no_of_inversions as max no of inversions could occur in the case when list has all the elements in strictly decreasing order ,i.e max_inversions=n(n-1)/2;

vstepano: 2016-12-15 19:36:07

I managed to solve this problem with 2 different programs. One using Merge Sort and one using the BIT (Binary Indexed Tree Peter M. Fenwick). My implementation that used Merge sort had a lot more code than the BIT one, but in the end the Merge sort solution was faster.

sergio471: 2016-12-08 21:39:57

too many WA because size_t is not necessarily unsigned long long

mohitgupta07: 2016-12-02 12:13:39

Got my error..did my code in eclipse..and just copy pasted it..forgot to remove my package line in the code...costed my NZEC :P :P :P


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