记录编号	286603	评测结果	AAAAAAAAAA
题目名称	谁是卧底	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-07-31 20:11:15	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
namespace mine{
	inline int getint(){
		static int __c,__x;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline long long getll(){
		static long long __x;
		static char __c;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline unsigned long long getull(){
		static unsigned long long __x;
		static char __c;
		__x=0;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		return __x;
	}
	inline void putint(int __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
	inline void putll(long long __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
	inline void putull(unsigned long long __x){
		static int __a[40],__i,__j;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
struct node{//AVL Balanced Tree
	int key,h,data;
	node *lch,*rch,*prt;
	node(int k=0):key(k),h(1),data(1),lch(NULL),rch(NULL),prt(NULL){}
	inline void refresh(){
		h=1;
		if(lch)h=max(h,lch->h+1);
		if(rch)h=max(h,rch->h+1);
	}
	inline int bal(){
		if(lch&&rch)return lch->h-rch->h;
		if(lch&&!rch)return lch->h;
		if(!lch&&rch)return -rch->h;
		return 0;
	}
};
node *root=NULL;
node *newnode(int=0);
void insert(node*,node* =root);
node *find(int,node* =root);
void lrot(node*);
void rrot(node*);
bool qorder(node*);
int n,x;
node *y;
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("leader.in","r",stdin);
	freopen("leader.out","w",stdout);
#endif
	getint();
	n=getint();
	for(int i=1;i<=n;i++){
		x=getint();
		y=find(x);
		if(y)y->data++;
		else insert(newnode(x));
	}
	if(!qorder(root)){
		putchar('-');
		putchar('1');
	}
	return 0;
}
inline node *newnode(int d){
	return new node(d);
}
inline void insert(node *x,node *rt){
	if(!root){
		root=x;
		return;
	}
	for(;;){
		if(x->key<rt->key){
			if(rt->lch)rt=rt->lch;
			else{
				rt->lch=x;
				break;
			}
		}
		else{
			if(rt->rch)rt=rt->rch;
			else{
				rt->rch=x;
				break;
			}
		}
	}
	x->prt=rt;
	//Insert Balance
	while(rt){
		rt->refresh();
		if(rt->bal()==2){//L
			x=rt->lch;
			if(x->bal()==1){//LL
				rrot(rt);
			}
			else{//LR
				lrot(x);
				rrot(rt);
			}
			rt=rt->prt;
		}
		else if(rt->bal()==-2){//R
			x=rt->rch;
			if(x->bal()==-1){//RR
				lrot(rt);
			}
			else{//RL
				rrot(x);
				lrot(rt);
			}
			rt=rt->prt;
		}
		rt=rt->prt;
	}
}
inline node *find(int x,node *rt){
	while(rt){
		if(x==rt->key)return rt;
		if(x<rt->key)rt=rt->lch;
		else rt=rt->rch;
	}
	return NULL;
}
inline void lrot(node *x){
	if(!x)return;
	node *y=x->rch;
	if(!y)return;
	y->prt=x->prt;
	if(x->prt){
		if(x==x->prt->lch)x->prt->lch=y;
		else x->prt->rch=y;
	}
	else root=y;
	x->prt=y;
	x->rch=y->lch;
	if(y->lch)y->lch->prt=x;
	y->lch=x;
	x->refresh();
	y->refresh();
}
inline void rrot(node *x){
	if(!x)return;
	node *y=x->lch;
	if(!y)return;
	y->prt=x->prt;
	if(x->prt){
		if(x==x->prt->lch)x->prt->lch=y;
		else x->prt->rch=y;
	}
	else root=y;
	x->prt=y;
	x->lch=y->rch;
	if(y->rch)y->rch->prt=x;
	y->rch=x;
	x->refresh();
	y->refresh();
}
inline bool qorder(node *x){
	if(!x)return false;
	if(x->data>(n>>1)){
		putint(x->key);
		return true;
	}
	if(qorder(x->lch))return true;
	return qorder(x->rch);
}
int hzoier=MAIN();
int main(){;}