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
anuj0503: 2016-07-05 13:33:25

BITS !! AC !!

truetubelight: 2016-04-25 07:44:50

Why does the tag say binary search if its using merge sort or BIT?

gautam: 2016-03-14 13:47:06

plz help i am getting WA ...need more testcases:(

minhthai: 2016-01-23 17:06:35

BIT cannot pass in java :(

iam_ss: 2016-01-13 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: 2016-01-13 19:22:25
raghav12345: 2016-01-05 16:14:13

easy if know inversion count method
using segment tree a nice question took 4 hours to understand : (

NEXES: 2016-01-01 18:04:27

use long long cost me 3 WA....!!!!

Arjav Patel: 2015-12-19 16:07:45

BIT and fast i/o 0.05! :)

MAYANK NARULA: 2015-12-15 15:47:52

This is one great problem....It has so many vivid approaches to solve other than merge-sort..
/*( however "ONLY ONE TRUTH PREVAILS" ~detective conan ... the problem says IT's A MURDER you know )*/

I tried BST first storing Left-Sub-Tree-sum but it might have lead to O(n^2) and so TLE....Through BST found an insight of a BIT solution..

AC with BIT in 0.18s ( w/o fast i/o like getchar_unlocked() )

Last edit: 2015-12-15 15:55:11
Anubhav Gupta: 2015-10-31 14:06:41

BIT rocks!!!


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