4. Let A be an array of n distinct numbers. Two elements of A are inverted if i but Au] > A. For example, in the array 12,3,1 the elements 3 and 1 are inverted. (a) (5 pts) List all the pairs of elements that are inverted in A 2.3,8.6,1), (b) (5 pts) Write down an array with flve numbers that has the maximum number of possible inversions. Let A and A2 be two arrays of n elements, such that Ai had more inver- Why? (10 pts) sions than A2. Which algorithm will be faster to sort using INSERTION-SORT Justify your answer) (c) (d) (10 pts) Describe a simple algorithm that outputs the number of inversions of an array. It can have any complexity. You don't need to write pseudocode (although you can), but your answer must be clear and easy to follow