An array is good if more than half of its elements are the same. Given an array A of size n, design a divide-and-conquer algorithm that checks whether the array is good, and if so, find the element that appears more than half of the times in O(nlogn) time. The domain from which the elements are taken is not necessarily ordered like integers, i.e. you cannot make comparisons like "Is A[i]>A[j] ?", but you can check whether two elements are the same in O(1) time. Briefly explain why your algorithm is correct. Write the recurrence relation for the running time and find its solution