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
minhthai:
20160123 17:06:35
BIT cannot pass in java :( 

iam_ss:
20160113 19:21:22
just a minor variation of INVCNT problem... got AC in 0.10s without BIT... just used merge sort (along with long long int) :) (took me 1 hour) Last edit: 20160113 19:22:25 

raghav12345:
20160105 16:14:13
easy if know inversion count method


NEXES:
20160101 18:04:27
use long long cost me 3 WA....!!!! 

Arjav Patel:
20151219 16:07:45
BIT and fast i/o 0.05! :) 

MAYANK NARULA:
20151215 15:47:52
This is one great problem....It has so many vivid approaches to solve other than mergesort..


Anubhav Gupta:
20151031 14:06:41
BIT rocks!!! 

free mind ;):
20150919 15:03:58
use long long for calculating sum!


SangKuan:
20150810 13:19:08
ac by mergesort . to many tle with common lisp,optimize after optimize,finally got ac.haha,no need to rewrite by c 

rk:
20150628 16:22:26
plz dont forget the zero case and declare array long long &finally done :)

Added by:  dce coders 
Date:  20120226 
Time limit:  1.259s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own Problem 