Find the Majority Element

easy

Given an array of size 'n', find the majority element. The majority element is the element that appears more than n/2 times. You may assume that the array is non-empty and the majority element always exist in the array.

Example 1

Input

[
  3,
  2,
  3
]

Output

Explanation. The number 3 appears twice which is more than half the size of the array (3/2 = 1.5).

Example 2

Input

[
  2,
  2,
  1,
  1,
  2,
  2
]

Output

Explanation. The number 2 appears four times which is more than half the size of the array (6/2 = 3).

Follow-up: Can you solve the problem in O(n) time and O(1) space complexity?

Constraints:

1 <= n <= 10^4 All the elements in the array will be integers.