$5.$ You are given an array A$[1..$n$]$ of n integers. We define an element x to be $$in the majority$$ if the set Ix $=\{$i : A$[$i$]=$ x$\}$ has size strictly more than n$/2.$ Note that any array A can have at most one element in the majority.

Given an array A$[1..$n$],$ design an O$($n$)$ time algorithm with the following guarantee: $$ If there is an element x which is in the majority, then it outputs x;

$$ else it outputs $$None$.$

You may assume that any two elements in the array can be compared in O$(1)$ time.

Hint: Suppose n is even. Pair the elements in the array in groups of $2.$ For each pair, if both elements are distinct, remove both elements from the array. If they are the same, retain exactly one of them in the array and discard the other. Prove that this step $($i$)$ shrinks the array size by at least $1/2$; $($ii$)$ the majority element $($if any$)$ continues to be the majority element in the reduced array as well. Also, pay special attention on how to handle the case when n is odd.