4. Let A[1n] be an array of n distinct numbers. If iA[j], then we say (i,j) is an inversion of A. Answer the following questions. a) What are the inversions in array {1,4,2,9,6,3} ? b) Consider the same array as in question a). Denote the number of inversions in the first half (aka {1,4,2} ) as a, then denote the number of inversions in the second half (aka{9,6,3}) as b, and denote the number of inversions between two halves as c. What are the values of a,b,c ? What's your observation about a,b,c and the answer from question a)? c) Consider the same array as in question a) and consider the same a,b,c as in question b). If I change the ordering inside both halves but not between halves, which value among a,b,c won't change? d) Present an algorithm of calculate the number of inversions of any n distinct numbers by modifying merge sort. Use your observation in question b). e) What is the running time of your algorithm? Why does your algorithm give the correct answer? (Hint: use the observations in b) and c).)