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
Added by:  dce coders 
Date:  20120226 
Time limit:  1.259s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All except: SCM chicken 
Resource:  Own Problem 
hide comments
abhijeet gusain:
20150219 21:10:30
@Gaurav necessary test cases are already given ... it may be that ur code has some input issues ... 

Gaurav sharma:
20141228 05:39:28
I'm getting wrong ans... plz give me d special test case.. 

vivek:
20141206 19:06:46
After one TLE accepted B 

Giribalaji:
20140918 12:35:21
Can someone please explain the given testcase? I am stuck there itself .. 

N0VICE:
20140808 18:16:53
Nice prblm :) 

Narendra yadav:
20140724 22:17:00
Is it solvable in O(n) ?


785227:
20140701 08:47:35
Beware of overflows. To avoid that, use long long throughout your code :) 

785227:
20140701 08:38:22
Handle the overflows during multiplication. Lots of WAs because of that 

monera:
20140527 07:41:09
My 50th :D 

Vipul Pandey:
20140105 20:50:02
remember "sum of all the numbers previously seen on the stairs which are smaller than the present number" and not smaller or equal.Equal costed me a WA. But still it is a nice one! 