Time Limit: 1 Sec Memory Limit: 128 MB
Vince is curious about how many swap times does Bubble Sort need to sort an array. He implements Bubble Sort Algorithm within 0.000001 second and gets the answer. Now, he wants to find a more efficient way to calculate. Could you solve it?
In Bubble Sort algorithm, you can only swap adjacent elements.
The first line will be an integer
For each test case, the first line will be an integer $n (1 ≤ n ≤ 10^5) $showing the length of array. Then there are n integers. It is guaranteed that each number will not exceed the limit of int.
For each case, please output the swap times that Bubble Sort needs to sort the array.
1
4
4 1 2 3
3