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
mohitgupta07: 2016-12-02 12:03:39

Simple .. BitMasking.. I mean Fenwick rocks :) :) Simple concept and simple logic.. Also can anyone explain why java gave NZEC for the same code in c++. Also take great care of choosing your data type. costed me 3 WA's . Nice ques and a good way to understand Fenwick :) .

rohan_12_11: 2016-11-16 10:34:27

use long long to get AC. Use ORDER STATISTIC BST algorithm.

Last edit: 2016-11-16 10:35:25
code_inception: 2016-11-10 18:57:11

good one to do with BIT .... will give more understanding of BIT

s_jindal00: 2016-11-10 16:49:21

For INPUT {5,2,3,8,6,1} : OUTPUT must be 8 but answer is 5 in sample input! Is it Wrong??????

munjal: 2016-09-23 20:18:01

long long long !!!!!!!!!!!!!!!!!!!
makes me 3 WA.

Romil Jain: 2016-08-16 05:59:44

Got several WA because of int.
Use long long int.
Also, a little weak test cases. It accepts A[i] == A[j] also as an inversion, whereas in question it is clearly mentioned A[i] > A[j].

kunal todi: 2016-08-05 11:06:06

used mergesort in c++..but getting TLE..

iharsh234: 2016-07-22 11:53:18

I ll do this some day!!
Done ! Too much WA after long time! ^_^
BIT is little tough to understand at first.

Last edit: 2016-07-29 15:36:55
iharsh234: 2016-07-22 11:53:18

Last edit: 2016-07-22 11:53:42
Bruce: 2016-07-20 11:10:11

Using mergesort and Python. Generated a test case with n = 16000 and response was instant. But when submitting I'm getting time limit exceeded. Are further optimisations required?


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