You are a visitor at a political convention with n delegates; each delegate is a member of exactly one political party. It is impossible to tell which political party any delegate belongs to; in particular, you will be summarily ejected from the convention if you ask anyone. However, you can determine whether any pair of delegates belong to the same party by introducing them to each other. Members of the same political party always greet each other with smiles and friendly handshakes, member of different parties always greet each other with angry stares and insults. Suppose more than half of the delegates belong to the same political party. Design a divide and conquer algorithm that identifies all member of this majority party and analyze the running time of your algorithm.
(Clarification: If we represent those delegates with array A[1..n), we cannot get result of A[i]< A[j]? or A[i] > A[j]? But we can get the result of A[i] == A[j]? in constant time.)