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
pratyushgadge1: 2023-10-13 20:41:33

i agree with @hraj123. don't use int. i used long long and got my solution accepted in the first try after the update;

orgil0127: 2023-06-27 06:57:03

HELLO world <2
(

hraj123: 2023-06-10 12:28:50

@new_mutant, it will overflow bcoz of array size not bcoz of array values, as total pair values can have upperbound as (n^2-n)/2 where n<=2e5.

Last edit: 2023-06-27 19:31:46
leonardodpv: 2023-05-08 02:10:41

Ojo con el numero de "inversions" que se pueden dar en casos muy grandes y ordenados.

Last edit: 2023-05-08 02:11:02
mddinislam: 2023-05-04 14:06:55

How the first test case answer is 2 ?

cprakash123: 2023-03-27 18:57:36

solving first time ...........

muaath5: 2023-03-11 09:54:46

This problem is solvable using:
1- Divide & Conquer (Merge Sort)
2- Segment tree
3- Fenweick tree (BIT)
4- Self-Balancing BST (indexed_set in C++)
5- Tries (Idk how does this work)

jmdalida11: 2022-11-07 14:44:15

I solved it using a binary tree :)

osman_goni_: 2022-08-08 17:59:27

Can this problem can be solved using Segment tree ?

spongecodes: 2022-01-11 20:03:21

why is my solution accepted in CPP 14 but giving WA in C++ ?


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