SPOJ.com - Problem INVCNT

INVCNT - Inversion Count

#number-theory #sorting

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⁷). 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

Submit solution!

hide comments

< Previous 23 24 25 26 27 28 29 30 31 32 33 Next >

	suyog patil: 2013-04-15 16:21:46 easy 1 with merge sort!!! try ur college assignment program..:P
	Akash Goel: 2013-04-15 16:21:46 changing the no of inversions to long long didnt help, still stuck at TLE. :(
	Aman Verma: 2013-04-15 16:21:46 Guya just long long dis cost me much .. not only change the inversion_count to long long but change the array holding it also to long long and no need to take the test case as long long and do use scanf and printf coz it also cost me 1 TLE :( but Finally AC :) <Use English, not internet gibberish. Comment left because it includes some relevant information. At least that's what I assume, because IT'S HARD TO READ!!> Last edit: 2012-12-20 07:53:47
	natsu: 2013-04-15 16:21:46 Thanks a lot guys.Its true .got AC after taking long long int for the no. of inversions
	Yashodhan S. Katte: 2013-04-15 16:21:46 @Rishabh use printf instead of cout and see.
	Haidar Abboud: 2013-04-15 16:21:46 No need for merge sort - you can just view the problem as a standard BIT exercise :P
	Rishabh Baid: 2013-04-15 16:21:46 would O(n log n) get accepted ? I tried using merge sort but got TLE.
	StupidGuy: 2013-04-15 16:21:46 Use long long int to count inversions.
	spock: 2013-04-15 16:21:46 wohooo..just changed the number of inversions to long long and got accepted.. :) Last edit: 2012-07-01 06:01:53
	data: 2013-04-15 16:21:46 @Anup use return 0

Submit solution!

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