DCEPC206  Its a Murder!
Once detective Saikat was solving a murder case. While going to the crime scene he took the stairs and saw that a number is written on every stair. He found it suspicious and decides to remember all the numbers that he has seen till now. While remembering the numbers he found that he can find some pattern in those numbers. So he decides that for each number on the stairs he will note down the sum of all the numbers previously seen on the stairs which are smaller than the present number. Calculate the sum of all the numbers written on his notes diary.
Input
First line gives T, number of test cases.
2T lines follow.
First line gives you the number of stairs N
Next line gives you N numbers written on the stairs.
Output
For each test case output one line giving the final sum for each test case.
Constraints
T<=10
1<=N<=10^5
All numbers will be between 0 and 10^6.
Example
Input: 1
5
1 5 3 6 4
Output: 15
hide comments
silent_1:
20200612 16:36:51
Similar Problems


scolar_fuad:
20191110 15:04:25
what a nice problem !


tanmay2904:
20190928 14:07:51
Got AC using simple BIT, without any coordinate compression.


prudhvi_495:
20190617 20:44:40
Same as "count inversion problem"


exesharkx:
20190405 22:19:37
Coordinate Compression + BIT 

chop_top:
20190107 06:40:05
If you use BIT then use coordinate compression, otherwise you'll get TLE. 

eagleshadow:
20180927 20:08:13
AC in one go :) 

karan_yadav:
20180810 21:09:49
Merge sort  0.07s


sinersnvrsleep:
20180720 20:04:51
hey @k0walsk1 may be when you are decreasing the value of i you are doing it till i >= 0 ; 

k0walsk1:
20180628 17:16:15
Can someone explain why using i & (i) for the bit functions gives TLE?? 
Added by:  dce coders 
Date:  20120226 
Time limit:  1.259s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 