Your mathematician friend get trouble again. He is trying to find the min sum of the inversion in the array, which is so samiliar to the problem we have taught him in homework. However, we can never leave friend in the lurch. Here is the problem:
Inversion : Let S be a sequence if i < j and S(i) > S(j), either the pair of places (i,j) or the pair of elements (S(i),S(j)) is called an inversion of S. Take [1,2,3,6,5,4] for example. (6,5) , (6,4) , (5,4) are inversion of the sequence [1,2,3,4,5,6]
Min sum of inversion: Calculate the sum of each inversion and find out the min sum. Take previous result (6,5), (6,4), (5,4) for example. Each sum of inversion will be 11, 10 and 9, then 9 is the min sum of inversion.
Note : If you are using visual studio, add #pragma warning(disable:4996) in the first line so that you can use scanf on your local machine.
T
N_1 S_1
N_2 S_2
...
N_T S_T
T : The number of the testcase (1<= T<= 10)
N_i : The size of input sequence (2<= N_i < 1000)
S_i : The positive sequence with each element in the sequence is less than 1000000
If there exists inversions, print out the min sum of inversions in the sequence
If there doesn't exists inversions, print out the string "No Inversion!"
(each output string must follow by a newline character)