Time Limit: 1 Sec  Memory Limit: 1 MB

Description

给你一个n个数的数列，其中某个数出现了超过n div 2次即众数，请你找出那个数。

Input

第1行一个正整数n。

第2行n个正整数用空格隔开。

Output

    一行一个正整数表示那个众数。

Sample Input

5
3 2 3 1 3

Sample Output

3

HINT

100%的数据，n<=500000，数列中每个数<=maxlongint。

zju2132 The Most Frequent Number

这题如果内存限制没那么坑的话直接哈希或者sort就水过了……

可是这限制实在太坑了

这题有个神算法：因为保证有一个数出现了超过n/2次，所以直接用num保存数字、用ans保存出现次数，每次出现和它不一样的就把ans抵消掉1，最后一定会出现保存的数的ans>1。最后num就是答案

话说用快速读入就是优越……

#include
    
     inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}int n,ans,num;int main(){	n=read();	while (n--)	  {	  	int x=read();	  	if (ans==0){ans=1;num=x;continue;}	  	if(x==num) ans++;else ans--;	  }	printf("%d",num);}