LSORT  Sorting is not easy
An Nelement permutation is an Nelement sequence of distinct numbers from the set {1, 2, ...,n}. For example the sequence 2,1,4,5,3 is a 5element permutation. P is an Nelement permutation. Your task is to sort P in ascending order. But because it is very simple, I have a new rule for you. You have two sequences P and Q. P is an Nelement permutation and Q is initially empty and formed by sorting P (i.e. finally Q = 1, 2, 3,... , N). You have to implement N steps to sort P. In the ith step, P has Ni+1 remaining elements, Q has i1 elements and you have to choose some xth element (from the Ni+1 available elements) of P and put it to the left or to the right of Q. The cost of this step is equal to x * i. The total cost is the sum of costs of individual steps. After N steps, Q must be an ascending sequence. Your task is to minimize the total cost.
Input
The first line of the input file is T (T ≤ 10), the number of test cases. Then descriptions of T test cases follow. The description of each test case consists of two lines. The first line contains a single integer N (1 ≤ N ≤ 1000). The second line contains N distinct integers from the set {1, 2, .., N}, the Nelement permutation P.
Output
For each test case your program should write one line, containing a single integer  the minimum total cost of sorting.
Example
N = 4
P = {4,1,3,2}
Step 1, Choose 3rd, P={4,1,2}, Q={3} , Cost=3
Step 2, Choose 1st, P={1,2}, Q={3,4} , Cost=2
Step 3, Choose 2nd, P={1}, Q={2,3,4} , Cost=6
Step 4, Choose 1st, P={}, Q={1,2,3,4}, Cost=4
The total cost is 15.
Another way to sort:
Step 1, Choose 4th, P={4,1,3}, Q={2} , Cost=4
Step 2, Choose 2nd, P={4,3}, Q={1,2} , Cost=4
Step 3, Choose 2nd, P={4}, Q={1,2,3} , Cost=6
Step 4, Choose 1st, P={}, Q={1,2,3,4}, Cost=4
The total cost is 18.
Input: 1 4 4 1 3 2
Output: 15
hide comments
mastik5h_1998:
20171219 09:02:53
easy if observed 

imperfectboy:
20170921 14:05:43
Took time but !!! AC in One go !!! 

ashish22_dwd:
20160912 21:03:46
Nice DP.. 

farhad chowdhury:
20160427 15:37:57
all problem r dam if c++ languages are not included 

xxbloodysantaxx:
20150711 11:35:55
I was trying to use D.S at the end realized that no D.S. is needed 
Added by:  Nguyen Minh Hieu 
Date:  20051220 
Time limit:  1s 
Source limit:  10000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ADA95 ASM32 BASH BF C CSHARP CPP CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PASGPC PASFPC PERL PHP PIKE PRLGswi PYTHON RUBY SCM qobi SCM guile ST TEXT WHITESPACE 
Resource:  Romanian National Contest 