How many inversions?

Humbertov Moralov in his student days, he is attended system engineering at “University of missing hill”. He was evaluated in its first course of Analysis of Algorithms (at the first half of 1997) with the following topics and questions: Inversions: Let A[1...n] an array of distinct integers of size n. If i < j and A[i] > A[j], then the pair (i,j) is called an inversion of A. Given the above definition about an inversion, Humbertov Moralov must answer the following ques- tions:

1. List all inversions in ⟨3, 2, 8, 1, 6⟩.
2. What array of size n, with all the numbers from the set 1, 2, 3, . . . , n has the largest amount of inversions? How many inversions?
3. Write an algorithm to determine the number of inversions in any permutation of n elements with θ(n log n) in the worst case run time. Humbertov Moralov answered questions 1. and 2. without any problem, but he was not able to solve the question 3 at time. Days later he thought the following solution: 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: inv←0 function Merge(A[], p, q, r) n1←q−p+1 n2←r−q create arrays L[1...n1 +1] and R[1...n2 +1] fori=1ton1 do L[i] ← A[p + i−1] end for forj=1ton2 do R[j] ← A[q + j] end for L[n1+1]←∞ R[n2+1] ← ∞ i←1 j←1 fork=ptordo if L[i] ≤ R[j] then A[k] ← L[i] i←i+1 else A[k] ← R[j] j←j+1 inv ← inv + n1−i + 1 end if end for end function

2/2 27: 28: 29: 30: 31: 32: 33: 34: function MergeSort(A[], p, r) if p < r then q ← ⌊(p + r)/2⌋ MergeSort(A[], p, q) MergeSort(A[], q + 1, r) Merge(A[], p, q, r) end if end function Will this code solve the problem? Just adding the lines 1 and 23 will be enough to solve the problem? Please help Humbertov Moralov to validate this solution! For this, you must implement this solution in any of the programming languages accepted by the ACM-ICPC and verify if the expected results are generated. Input The input may contain several test cases. Each input case begins with a positive integer n (1 ≤ n ≤ 106) denoting the length of A, followed by n distinct lines. Each line contains a positive integer from array A. For i ∈ [1,n], will meet that 0 ≤ A[i] ≤ 108. The input ends with a test case in which n is zero, and this case must not be processed. Output For each test case, your program must print a positive integer representing the total number of inversions in the array A. Each valid test case must generate just one output line. Sample Input 5 3 2 8 1 6 5 5 4 3 2 1 1 10 0 Sample Output 5 10 0