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
sabkx: 2021-10-03 07:06:22

EZ AC in second go! use long long instead of int. Merge sort works with 0.11 second

jdmoyle: 2021-08-19 06:33:52

Fenwick Tree :D, return type long long int

ss_sri: 2021-08-16 11:15:07

IDK but i am not able to solve it using merge sort, it says SEGMENTATION FAULT.

amish3: 2021-06-30 06:33:50

Getting TLE, even after using merge sort algorithm and scanf/printf. Any idea. Why it is so

jasperj1: 2021-06-23 16:15:35

Can be easily solved using the Merge Sort function. Just add some checks while merging and you are good to go.

loser_404: 2021-06-04 10:02:16

Similar problems using Ordered_set:
Points on Line(CF)
Sliding Median(CSES)
Sliding Cost(CSES)
Inversion Count(SPOJ)

vishal55: 2021-05-15 10:21:11

A good problem to learn PBDS if you use C++
https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/

dvjpy786: 2021-04-09 10:29:22

Ac in one go using segment tree

s_sarvesh_18: 2021-03-31 07:07:42

modified merge sort on passing by reference and using printf/scanf (instead of cin/cout ) gets accepted.
Apparently differences are too big between cin/cout and scanf/printf in SPOJ.

rahulreddevil: 2021-03-29 14:22:52

Solved using Fenwick Tree !


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