template<typename Type,int Size,Type NONE>
class FHQTreap
{
	protected:
		struct node
		{
			Type data;
			int size,r,ls,rs;
			int lazy;
		};
		node v[Size];
		int root=0,tot=0;
		int new_p(Type x)
		{
			v[++tot]={x,1,rand(),0,0};
			return tot;
		}
		void pushup(int index)
		{
			v[index].size=1+v[v[index].ls].size+v[v[index].rs].size;
		}
		void pushdown(int index)
		{
			if(!v[index].lazy || !index)return;
			v[v[index].ls].lazy+=v[index].lazy;
			v[v[index].rs].lazy+=v[index].lazy;
			v[index].data+=v[index].lazy;
			v[index].lazy=0;
		}
		void split(Type x,int index,int &ls,int &rs)
		{
			if(!index){ls=rs=0;return;}
			pushdown(index);
			if(v[index].data<=x)
				ls=index,split(x,v[index].rs,v[index].rs,rs);
			else
				rs=index,split(x,v[index].ls,ls,v[index].ls);
			pushup(index);
		}
		int merge(int ls,int rs)
		{
			if(!ls || !rs)return ls+rs;
			if(v[ls].r>v[rs].r)
			{
				pushdown(ls);
				v[ls].rs=merge(v[ls].rs,rs);
				pushup(ls);
				return ls;
			}
			else
			{
				pushdown(rs);
				v[rs].ls=merge(ls,v[rs].ls);
				pushup(rs);
				return rs;
			}
		}
		Type get_topk(int x,int index)
		{
			pushdown(index);
			int lss=v[v[index].ls].size;
			if(x==lss+1)return v[index].data;
			if(x<lss+1) return get_topk(x,v[index].ls);
			else  return get_topk(x-lss-1,v[index].rs);
		}
	public:
		int size()
		{
			return v[root].size;
		}
		bool empty()
		{
			return !size();
		}
		void push(Type x)
		{
			int ls,rs;
			split(x,root,ls,rs);
			root=merge(merge(ls,new_p(x)),rs);
		}
		void pop(Type x)
		{
			int ls,p,rs;
			split(x,root,ls,rs);
			split(x-1,ls,ls,p);
			p=merge(v[p].ls,v[p].rs);
			root=merge(merge(ls,p),rs);
		}
		int count(Type x)
		{
			int ls,p,rs;
			split(x,root,ls,rs);
			split(x-1,ls,ls,p);
			int ans=v[p].size;
			root=merge(merge(ls,p),rs);
			return ans;
		}
		int get_rank(Type x)
		{
			int ls,rs;
			split(x-1,root,ls,rs);
			int ans=v[ls].size+1;
			root=merge(ls,rs);
			return ans;
		}
		Type get_topk(int x)
		{
			return get_topk(x,root);
		}
		Type get_prev(Type x)
		{
			int ls,rs;
			split(x-1,root,ls,rs);
			if(!ls)return -NONE;
			int ans=get_topk(v[ls].size,ls);
			root=merge(ls,rs);
			return ans;
		}
		Type get_next(Type x)
		{
			int ls,rs;
			split(x,root,ls,rs);
			if(!rs)return NONE;
			int ans=get_topk(1,rs);
			root=merge(ls,rs);
			return ans;
		}
};