题目内容

给定一个大小为 $n$ 的整数数组 $nums$，请返回数组中的多数元素。

多数元素是指在数组中出现次数大于 $\lfloor n/2 \rfloor$ 的元素。

可以保证数组非空，并且给定的数组中一定存在多数元素。

输入描述

第一行输入一个整数 $n$，表示数组 $nums$ 的长度。

第二行输入 $n$ 个整数 $nums_i$，表示数组中的各个元素，相邻整数之间用空格分隔。

约束

$1 \le n \le 5 \times 10^4$

$-10^9 \le nums_i \le 10^9$

输入保证数组中一定存在多数元素。

输出描述

输出一个整数，表示数组 $nums$ 中的多数元素。

样例 $1$

输入

3
3 2 3

输出

3

说明

数字 $3$ 在数组中出现了 $2$ 次。

因为 $2>\lfloor 3/2 \rfloor$，所以 $3$ 是数组中的多数元素。

样例 $2$

输入

7
2 2 1 1 1 2 2

输出

2

说明

数字 $2$ 在数组中出现了 $4$ 次。

因为 $4>\lfloor 7/2 \rfloor$，所以 $2$ 是数组中的多数元素。