One day, your mathematician friend get trouble again. He is trying to find the max sum of the inversion in the array, but the array is too large to calculate by handcraft method. He ask you to help him finish the job and write down the problem below:
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 elemets (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]
Max sum of inversion: Calculate the sum of each inversion and find out the max sum. Take previous result (6,5), (6,4), (5,4) for example. Each sum of inversion will be 11, 10 and 9, then 11 is the max sum of inversion.
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 max 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)