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

khoaph: 2021-03-16 08:18:55

Finally get AC by using binary search tree

yasser1110: 2021-02-24 12:25:00

Return type long long vs int tripped me up.

Last edit: 2021-02-24 12:25:12
goku123456: 2021-02-03 19:32:52

A really good sum. But wasted so much time in tle. Pass by reference to remove tle.

vishalmahavar: 2021-01-21 09:16:47

How is it related to graphs and bitmasks??

affan12347: 2021-01-15 16:03:56

monka s . naive array approach doesnt work , gives tle

Last edit: 2021-01-15 16:04:21
tejasreddyk: 2021-01-14 16:29:27

monkagiga count normal variable and std::count messed me up

sudo_s: 2021-01-01 15:07:07

Very Weak test Cases.
try a={84, 2, 37, 3, 67, 82, 19, 97, 91, 63, 27, 6, 13, 90, 63, 89, 100, 60, 47, 96, 54, 26, 64, 50, 71, 16, 6, 40, 84, 93, 67, 85, 16, 22, 60 };
my solution gave output 245 but it got accepted , correct answer=290

[NG]: Your case is invalid (*distinct* integers).

Last edit: 2021-01-01 22:42:20

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