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。

 

经典题了，直接放代码吧。

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define ren for(int i=first[x];i;i=next[i])using namespace std;const int BufferSize=1<<16;char buffer[BufferSize],*head,*tail;inline char Getchar() { if(head==tail) { int l=fread(buffer,1,BufferSize,stdin); tail=(head=buffer)+l; } return *head++;}inline int read() { int x=0,f=1;char c=Getchar(); for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1; for(;isdigit(c);c=Getchar()) x=x*10+c-'0'; return x*f;}int last,cnt,x;int main() { dwn(i,read(),1) { x=read(); if(!cnt) last=x,cnt=1; else if(last==x) cnt++; else cnt--; } printf("%d\n",last); return 0;}