给定一个大小为 n 的整型数组 a，找到其中的多数元素，多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
输入
第一行输入一个整数 n \ (1 \leq n \leq 10^4) 代表数组的长度。
第二行输入一行数字代表数组 a \ (1 \leq a_i \leq 10^4)，数字与数字之间用空格间开。
保证给定的数组总是存在多数元素。
输出
输出一个整数代表数组的多数元素。
样例
| 标准输入 复制文本 |
3 1 1 1 |
| 标准输出 复制文本 |
1 |
| 标准输入 复制文本 |
7 4 1 2 3 3 3 3 |
| 标准输出 复制文本 |
3 |
| 标准输入 复制文本 |
9 4 2 2 2 2 21 23 23 2 |
| 标准输出 复制文本 |
2 |
提示
如果数 a 是数组 n 的众数，如果我们将 n 分成两部分，那么 a 必定是至少一部分的众数。