SPOJ.com - Problem INVCNT

INVCNT - Inversion Count

#number-theory #sorting

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⁷). 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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 11 Next >

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

Submit solution!

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