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
pirate_joker1: 2019-08-15 12:14:19

solved it using PBDS

bogdanvlad: 2019-07-09 00:47:06

AC in one go using merge sort, very nice problem

howdy_1999: 2019-07-08 16:00:46

Divide and conquer approach

sajalagrawal14: 2019-07-01 16:11:36

good problem.
can be solved using segment tree, fenwick tree, and merge sort

Last edit: 2019-07-01 16:11:56
killerjay: 2019-06-25 19:18:46

just store the element and index in pair and after that sort pair in decreasing order with respect to first element
and then we have to just find the values of indexes which are smaller then the ith indexe keep the count and sum it simple BIT AC in one go
loved this question my first on BIT

Last edit: 2019-06-25 19:22:45
smrtdvlpr: 2019-06-25 12:26:45

Great problem, can be done easily using divide and conquer.

rohan_24: 2019-05-28 10:17:07

can anyone tell,how to solve this by BIT?

hetp111: 2019-05-27 08:33:53

Great problem...! can be done using D&C, BIT or Segment Tree...

walter_whitee: 2019-04-24 00:27:33

AC in one go using divide and conquer technique :D

gabrijel: 2019-03-27 23:41:09

Yes, output can be up to n^2 so O(n^2) should definitely pass.


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