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
mohitgupta07:
20161202 12:03:39
Simple .. BitMasking.. I mean Fenwick rocks :) :) Simple concept and simple logic.. Also can anyone explain why java gave NZEC for the same code in c++. Also take great care of choosing your data type. costed me 3 WA's . Nice ques and a good way to understand Fenwick :) . 

rohan_12_11:
20161116 10:34:27
use long long to get AC. Use ORDER STATISTIC BST algorithm.


code_inception:
20161110 18:57:11
good one to do with BIT .... will give more understanding of BIT 

s_jindal00:
20161110 16:49:21
For INPUT {5,2,3,8,6,1} : OUTPUT must be 8 but answer is 5 in sample input! Is it Wrong?????? 

munjal:
20160923 20:18:01
long long long !!!!!!!!!!!!!!!!!!!


Romil Jain:
20160816 05:59:44
Got several WA because of int.


kunal todi:
20160805 11:06:06
used mergesort in c++..but getting TLE..


iharsh234:
20160722 11:53:18
I ll do this some day!!


iharsh234:
20160722 11:53:18
Last edit: 20160722 11:53:42 

Bruce:
20160720 11:10:11
Using mergesort and Python. Generated a test case with n = 16000 and response was instant. But when submitting I'm getting time limit exceeded. Are further optimisations required? 
Added by:  Paranoid Android 
Date:  20100306 
Time limit:  3.599s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: PERL6 