Question 3: [30 points] Inversions: An important part of sorting, higher the number of inversions, longer the run time to sort the elements) Given any list of n numbers, there are pairs of numbers as you remember from Discrete Math. nn(n-1) For example, the list (1, 3, 5, 4, 2, 6) contains the following 15 pairs (3. 5) (3,4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6) You may note that 11 of these pairs of numbers are in order Let 4/1M) be an array of n distinct numbers. If i 407. then the pair ri, j) Is called inversion of A. (Please note that for array A indexing starts from 1) Using the example above indexes (3,4) is an inversion of A because 3rd index in array A contains 5 and 4th index in array A contains 4 and clearly A[31 > A[4] Using this example list 5 inversions of the array A = [2.3.8.6.1], please keep in mind that indexing starts from 1. Remember that inversions are specified by indices rather than by the values in the array a) b) What array with elements from the set (1,2, ...n) has the most inversions? How many does it have? What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer c)