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:
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