主元素算法，线性复杂度，比较机智的思路，简单说就是维持计数，相同的就+，相异就-，计数为0记录新的数

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

const int maxn= 1e6+5;
int n, x;

int main()
{
	while (EOF!= scanf("%d", &n)){
		int a= -1, c= 0;
		for (int i= 0; i< n; ++i){
			scanf("%d", &x);
			if (0== c){
				a= x;
				++c;
			}
			else if (x== a){
				++c;
			}
			else{
				--c;
			}
		}

		printf("%d\n", a);
	}

	return 0;
}