#include<algorithm>
template<typename T,int siz>
class lheap{//小根堆
	public:
		lheap(void):si(0){}
		~lheap(){}
		const int size(void)const{return si;}
		const int memo(void)const{return siz;}
		void put(T a){
			if(si==size){
				throw "Heap has already full.";
			}
			he[++si]=a;
			int now=si,next;
			while(now){
				next=now/2;
				if(he[next]<he[now])break;
				std::swap(he[next],he[now]);
				now=next;
			}
		}
		const T pop(){
			if(si==0){
				throw "Heap has already empty.";
			}
			T res=he[1];
			he[1]=he[si--];
			int now=1,next;
			while(now*2<si){
				next=now*2;
				if(next+1<=si&&he[next+1]<he[next])next++;
				if(he[now]<he[next])break;
				std::swap(he[now],he[next]);
				now=next;
			}
			return res;
		}
		const T& top(void){return he[1];}
	private:
		T he[siz+1];
		int si;
};
template<typename T,int siz>
class bheap{//大根堆
	public:
		bheap(void):si(0){}
		~bheap(){}
		const int size(void)const{return si;}
		const int memo(void)const{return siz;}
		void put(T a){
			if(si==size){
				throw "Heap has already full.";
			}
			he[++si]=a;
			int now=si,next;
			while(now){
				next=now/2;
				if(he[next]>he[now])break;
				std::swap(he[next],he[now]);
				now=next;
			}
		}
		const T pop(){
			if(si==0){
				throw "Heap has already empty.";
			}
			T res=he[1];
			he[1]=he[si--];
			int now=1,next;
			while(now*2<si){
				next=now*2;
				if(next+1<=si&&he[next+1]>he[next])next++;
				if(he[now]>he[next])break;
				std::swap(he[now],he[next]);
				now=next;
			}
			return res;
		}
		const T& top(void){return he[1];}
	private:
		T he[siz+1];
		int si;
};