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
aman_sachin200:
20180605 00:28:46
Simple implementation of FENWICK Trees!!Beware of 0!!!Try INVCNT after this one :) 

anirudnits:
20180524 09:23:14
use long long everywhere to prevent overflows. Cost me 2 WA's 

harsh27:
20180209 16:08:48
it take 2 hour to do for soln with bst (nlogn) and TLE error


tarun2797:
20171129 15:07:26
try with trie... 

sohailwiiierd:
20171009 12:08:38
binary search giving me TLE


rajeev_899:
20170622 14:40:11
Double Century :) :) :) :) 

siddharth_0196:
20170610 16:27:23
O(nlog(max_element)) > TLE


imperfectboy:
20170608 18:40:55
long long cost me 2WA !!! 

nky_007:
20170530 06:23:27
Easy one using merge sort.


sourav15102:
20170529 19:13:24
Why am I getting TLE for using Binary search tree in this problem? 
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 