Let A[1..n] be an array of n elements. An element x is called a majority element in A[1..n] if Card({ i | A[i] = x }) > 2n/3.

Give an O(n) algorithm that decides whether A[1..n] contains a majority element, and if so finds it.