DCEPC206 - Its a Murder!

no tags 

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:2012-02-26
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
i_am_looser: 2015-05-24 09:45:41

Good question =)

Madhav: 2015-04-02 11:40:28

good question!!

abhijeet gusain: 2015-02-19 21:10:30

@Gaurav necessary test cases are already given ... it may be that ur code has some input issues ...

Gaurav sharma: 2014-12-28 05:39:28

I'm getting wrong ans... plz give me d special test case..

vivek: 2014-12-06 19:06:46

After one TLE accepted B|

Giribalaji: 2014-09-18 12:35:21

Can someone please explain the given test-case? I am stuck there itself ..

||N0VICE||: 2014-08-08 18:16:53

Nice prblm :)

Narendra yadav: 2014-07-24 22:17:00

Is it solvable in O(n) ?
Solved it using BIT. But my silly mistakes cost me many WA.

785227: 2014-07-01 08:47:35

Beware of overflows. To avoid that, use long long throughout your code :)

785227: 2014-07-01 08:38:22

Handle the overflows during multiplication. Lots of WAs because of that