题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入格式

第一行输入一个整数 $n$，表示数组大小。

第二行输入$n$个数字，每个数字中间以空格隔开。

输出格式

输出多数元素。

样例

3
3 2 3

3

7
2 2 1 1 1 2 2

2

数据范围

对于所有测试数据，保证：$1 \leq n \leq 5*10^4$,$-10^9 <= nums[i] <= 10^9$。