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
ragwave: 2016-05-12 21:43:24

use unsigned long long int for counting inversions.

shan2new: 2016-04-28 02:43:41

Modification of Merge Sort. Did the same question from CLRS :)

sahilagg06: 2016-04-17 10:43:09

Read BIT from ch2 of "CP by Steven Halim" and it will be a piece of cake. :)

pablod_bc: 2016-03-18 05:32:48

Last edit: 2016-03-19 12:07:28
arthur: 2016-02-27 13:10:49

Can be solved using segment, BIT, range trees. Also try and solve LIS using segment trees. All solutions should be O(nlgn)

Devashish Mathur: 2016-02-16 06:47:14

Cheated.. but Loved it..

lakshay_v06: 2016-01-28 13:01:16

If this is the first question you are trying to do using BIT, then please try some other questions of BIT before this one.... It took me quite some while to figure out the logic behind this question's BIT implementation.... :)

ibrahim5253: 2016-01-24 20:49:14

Thanks @Kartik. I would have toiled for hours to figure out the WA.

amit013: 2016-01-21 19:52:28

nice problem !!!

Papai: 2016-01-11 00:41:57

Last edit: 2016-01-11 00:52:52

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