1. Given an integer array A, Ali] and Alil are inverted if i Ai]. Consider the following array with 10 elements. In it, 1 (A[2] 4), so 5-4 is an inversion. In this array there are a total of 15 inversions: 4-2, 4-3, 5-2, 5-3, 5-4, 8-2, 8-3, 8-6, 8-7, 9-2, 9-3, 9- 6, 9-7,9-8, and 10-7 1 5498236107 (a) [3 pts] Write a divide-and-conquer algorithm to count the number of inversions in an integer array A of size n. (b) [2 pts] Set up a recurrence relation for the run time of your algorithm in the worst case. Briefly explain how each term in the recurrence arises. Solve the recurrence using the Master Method