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(in 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 A/1..n/ be an array of n distinct numbers. If i Afil, then the pair (i, i) 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[3]> A[4]. a) 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. does it have? inversions in the input array? Justify your answer. b) What array with elements from the set {1,2, ...n} has the most inversions? How many c) What is the relationship between the running time of insertion sort and the number of