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
Rajat (1307086): 2015-01-18 19:49:38

Divide and Conquer.

Yashpal: 2015-01-05 15:58:36

AC using BIT,Segment Tree,Merge Sort, Trie !!
Loved this problem !! ;)

agaurav77: 2014-12-26 12:13:29

Simple cin/cout IO with the divide and conquer paradigm (remember to use long long), AC :)

rishabh aggarwal: 2014-12-04 17:32:23

use long long to get ac...

Last edit: 2014-12-04 17:32:47
Rafael Perrella: 2014-12-04 00:49:37

@benevides
resp should be long long

benevides: 2014-12-03 20:46:22

i dont get it,why doesn't it work <snip>

Last edit: 2022-06-26 16:04:56
arun : 2014-11-25 17:55:04

Real please AC in 1st go!!! use BIT
And take care of repeat element.

Last edit: 2014-11-25 17:56:04
[Lakshman]: 2014-11-12 12:19:45

@Abi you have declared count as long long and your mergesort is returning int , So declare mergesort and merge long long instead. Hope this helps.

Last edit: 2014-11-12 12:25:19
Abi: 2014-11-12 06:59:38

I dont know ....why iam getting WA :(
pls anyone help
<snip>

Last edit: 2022-06-26 16:05:00
surayans tiwari(http://bit.ly/1EPzcpv): 2014-11-08 12:29:10

acce using merge ,, got acc using fast i/o with bit

Last edit: 2014-11-08 12:44:38

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