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
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

terminator_pk: 2020-02-07 19:18:21

Last edit: 2020-02-08 12:55:30
savage_19: 2020-02-04 08:30:10

1. Do it with merge sort first.
2. Then try it with Fenwick or Binary indexed tree.
3. After that, if you want you can solve it using,
* AVL tree (Self-balancing BST)
* Segment tree
4. By trying out these things, you will get used to those data structures and algorithms.
5. Also use long data type in java and long long in c++ to count the number of inversions.

Last edit: 2020-02-04 08:32:27
avsd_47: 2020-01-21 18:22:23

Caution:the answer you are going to print must be of type long long costed me 3 wa's.

sangmai: 2020-01-17 03:14:50

AC in one go using merge sort

sajalagrawal14: 2019-12-03 13:46:03

Can be solved Using
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

codefresher: 2019-11-22 22:44:54

Good one....solved using merge sort tree...segment tree???

abhishak69: 2019-11-22 21:51:35

my first fenwick tree question :)

ishancosmos25: 2019-11-10 05:27:54

Used BIT and inversions count to solve the problem.


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