3. Consider an array A containing n distinct integers. The local minimum of A is an integer r such that x = Afor some 0 i n, with Ali-I] Ali] and A [i] AB+ 1]. ln other words, a local minimum r is less than its neighbors in A (for boundary elements, there is only one neighbor). We want to solve the problem of finding a local minimum. Note that A might have multiple local minima, but you only need to locate and return one (a) Describe an efficient divide-and-conquer algorithm that solves this problem. (b) Prove your algorithm is correct and runs in time O(logn). [6 marks] 4 marks]