An array A[1... n] is said to have a majority element if more than half of its entries are the same. Given an array, design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form "is A[i] > A[j]?". (As an example, think of the array elements as PDF files.) However, you can answer questions of the form "is A[i] = A[j]?" in constant time. Give a Theta(n log n) divide-and-conquer algorithm to solve this problem. Remember, a complete answer includes an algorithm description, an algorithm, and a analysis