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
studyfather: 2017-07-24 13:50:35

use merge sort and AC!!!

ani_geek9654: 2017-07-01 13:37:46

AC in 1
Just MergeSort

hzshang: 2017-06-30 18:26:07

Binary tree, easy :P

kartiks22: 2017-06-26 09:40:03

took me 2 hours to figure out long long mistake !!!

plab0n: 2017-06-19 21:54:15

I am getting TLE in my merge_sort approach. Plz help me how can I make my code efficient.
Here is my Code link: https://paste.ubuntu.com/24901461/
Thanks in advance :)

lord_poseidon: 2017-06-19 07:24:22

Easy one AC in one go

prodipdatta7: 2017-06-12 18:05:30

AC in one go!!
Only Merge Sort..

abdrakhman: 2017-06-02 09:48:56

AC in one go))))

anurag44: 2017-05-25 04:38:39

Core concept of sorting algorithm..

thefriction: 2017-05-02 14:53:24

thanks @fane_faiz :)


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