Let x1, . . , xn be an array x of n distinct numbers. we say two numbers xi and xj form an inversion if i < j but xi > xj . (a) what are the maximum and minimum possible numbers of inversions for an array of size n? provide examples of arrays attaining these two numbers. (b) prove that array x is sorted in increasing order if and only if the total number of inversions in x is zero. (c) design an o(n 2 )-time brute-force algorithm to count the total number of inversions in x. (d) consider the following divide-and-conquer approach for counting the number of inversions in x: partition x into xl = {x1, . . , xn/2} and xr = {xn/2+ }. all we need to do is to add nl (total number inversions in xl), nr (total number inversions in xr), and the number of inversions occur between xl and xr. complete the design and analysis this algorithm. (e) design another efficient algorithm that counts the number of inversions using binary search trees.