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
shreeshiv: 2017-02-20 10:13:59

What is WA and AC??

nilabja16180: 2017-02-13 13:47:11

A great BIT problem

fane_faiz: 2017-02-09 10:21:48

Don't forget to use long long, caused me 2 WA.

sks4903440: 2017-02-07 20:24:44

Don't forget to use long long.

akash_23: 2017-02-07 18:53:16

did using BIT, easy AC! tag helped me to get the idea :P

zhanbolat: 2017-01-22 17:32:14

I didn't get relation between graph theory and this problem.
Can somebody share with #graph,#shortest path solution ?

Last edit: 2017-01-22 17:33:06
muneebaadil: 2017-01-20 18:15:37

Oh damn you long long! Probably a lesson for me to be conscious with data types from now on..

scorpion_ajay: 2017-01-19 11:44:24

best for learners, learning overloaded, spent two days, came out of no hope.
Finally AC :)

gauravgb21: 2016-12-29 07:59:30

jst modify the mergesort algorithm
and thts all!!

aditya930: 2016-12-27 23:53:59

use enhanced merge sort and long long to get AC !!


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