样例下载

提示

注意内存限制。

题目描述

有 N 头奶牛，第 i 头奶牛的身高为 Hi。

FJ 惊奇地发现，有超过半数的奶牛具有相同的身高，记为 h。

请你求出 h 的值。

多组数据。

输入

每个测试点含多组数据，但不超过四组。

对于每组数据：

• 第一行：一个整数 N；
• 第二行：N 个整数 Hi。数据保证有一个整数的出现次数超过半数。

当读取到 N = 0 时表示输入结束。

输出

若干行，每组数据答案占一行。

样例输入

5
1 1 2 2 2
0

样例输出

2

数据范围

100% 的数据：1 ≤ N ≤ 2×10^7, 1 ≤ Hi ≤ 10^9

每组数据保证答案 h 的出现次数超过半数。

特别提醒

本题每个测试点时间限制 1 S，空间限制 10 MiB。

由于数据量较大，请使用较快的读取方式。