题目描述

给你一个长度为$N$的数组$a$,$a$内有一个元素的个数大于数组总长度的一半。 例如$a=[1,2,2,2]$,$2$这个元素的个数为3大于数组长度的一半也就是2。 再比如$a=[1,2,2]$,$2$这个元素的个数为2大于数组长度的一半也就是1(对于奇数要向下取整). 现在你的任务是给你$a$让你找到这个个数大于数组元素一半的数。

注意这个题在八股书上要求必须是$O(N)$的时间复杂度和空间复杂度，所以本题也是如此。

也就是说你不要想着排序然后找$a[\\frac{n+1}{2}]$,这样的话时间复杂度是$O(NlogN)$是会给卡掉的。

对于空间你也不要想着开什么map或者unordered_map,空间也是给卡的死死的,顶多就开一个记录的数组。

输入格式

第一行输入一个正整数$N (1\\le N \\le 5\ imes 10^6)$代表数组$a$的长度

接下来$N$个数$a_i (1\\le a_i\\le 10^{18})$

输出格式

一行一个数代表答案

样例

4 
1 2 2 2

2

3 
1 2 2 

2

4 
2 2 1 2

2

提示

本题的输入非常的巨大，经过我的测试需要使用快速读入，请在你的代码内加入以下的快速读入，要不会读入超时。

inline long long read() 
{ 
	long long x=0,y=1;char c=getchar(); 
	while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();} 
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 
	return x*y; 
}