An array A[0..n-1] stores n distinct integer numbers. We say that a pair (A[i], A[j]) is bad, if i A[j].

Problem 4. An array Al0.. 1 stores n distinct integer numbers. We say that a pair (Al], Aj]) is bad, if i Aj]. Let bad(A) be the number of bad pairs in A (a) Given n, find an array A with minimum number of bad pairs. Also, find an array A with maximum number of bad pairs. Write the number of bad pairs in each case (b) Suppose that the numbers in A cannot be read and the only available operation is the comparison of two of elements in A. Explain the correctness and the running time of your algorithm