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
kprock41951:
20200803 20:17:03
Last edit: 20200803 20:17:46 

coolboy7:
20200730 15:26:02
answer will be in range of long long 

robosapien:
20200721 18:11:41
use long long. 

dardev:
20200703 16:48:44
The concept is covered very well here > https://www.youtube.com/watch?v=7_AJfusC6UQ 

mukul202:
20200519 17:39:01
Just solved this question using:


picchi_67:
20200506 05:46:10
Can be Solved Easily with merge sort.


mt6170078:
20200421 16:14:30
why tag of Bitmask? how to use Bitmask here?? 

yourmom__:
20200421 07:40:01
I see the question. Okay. Thought of a simple O(n^2) algo. Then I submit and get TLE. Offcourse. Then I see the commenst section. People are commenting about Fenwick trees? Segment trees? Self balancing BST? Now WHAT THE FUCK are these? Spent 23 days learning their basics. People who are getting TLE, spend sometime learning these new data structures, ans dont give up.


offamitkumar:
20200329 10:47:02
Solved it With


vishesh_2308:
20200312 10:57:36
https://youtu.be/B29dVmpIpn0

Added by:  Paranoid Android 
Date:  20100306 
Time limit:  3.599s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: PERL6 