You are given an array, A[1..n] of n (possibly repeated) numbers. You task is to check if there is a majority number. A number is a majority number of A if more than half of numbers in A equal to it. (a) Design an O(nlogn) algorithm which calls, without implementing, function HeapSort(A). Prove the complexity of your algorithm. (b) Design an O(nlogn) divide-and-conquer algorithm which does not involve sorting. Prove the complexity of your algorithm. Note that both of the algorithms should only spend constant memory space aside from array A.