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: 2020-08-03 20:17:03

Last edit: 2020-08-03 20:17:46
coolboy7: 2020-07-30 15:26:02

answer will be in range of long long

robosapien: 2020-07-21 18:11:41

use long long.

dardev: 2020-07-03 16:48:44

The concept is covered very well here -> https://www.youtube.com/watch?v=7_AJfusC6UQ

mukul202: 2020-05-19 17:39:01

Just solved this question using:
1)merge sort
2)fenwick tree
3)segment tree
Now trying with tries:)

picchi_67: 2020-05-06 05:46:10

Can be Solved Easily with merge sort.
Great problem for BIT Practice....Use " Long Long Int ".
Hint: use element value.

mt6170078: 2020-04-21 16:14:30

why tag of Bitmask? how to use Bitmask here??

yourmom__: 2020-04-21 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 2-3 days learning their basics. People who are getting TLE, spend sometime learning these new data structures, ans dont give up.
Happy Coding bois

edit: The answer can be >2^32, so use long. Things like this should be mentioned in the statment. I wasted 30 mins just because of this

Last edit: 2020-04-21 10:15:37
offamitkumar: 2020-03-29 10:47:02

Solved it With
1)Segment tree
2)fenwick tree (with or without cordinate compression)
3)merge sort
4)policy based data structure in c++ (vary small code, even smaller than fenwick tree)
5)Self Balancing Bst
6) Trie Data Structure (This one is interesting)

Last edit: 2020-03-29 10:47:44
vishesh_2308: 2020-03-12 10:57:36

https://youtu.be/B29dVmpIpn0
Check this video if you are not able to understand the merge sort algo


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