Given an array of size n, return the majority element — the element that appears more than ⌊n/2⌋ times. You may assume the majority element always exists.

Example 1:

Input:  3 2 3
Output: 3

Example 2:

Input:  2 2 1 1 2 2 2
Output: 2

Input format: Space-separated integers.