template<typename Type,int Size,Type NONE>
class Treap
{
	protected:
		struct node
		{
			Type data;
			int size,t,ran,ls,rs;
		};
		node v[Size];
		int root=0,tot=0;
		void pushup(int index)
		{
			v[index].size=v[index].t+v[v[index].ls].size+v[v[index].rs].size;
		}
		void zig(int &index)//右旋 
		{
			int q=v[index].ls;
			v[index].ls=v[q].rs;
			v[q].rs=index;
			v[q].size=v[index].size;
			pushup(index);
			index=q;
		}
		void zag(int &index)//左旋
		{
			int q=v[index].rs;
			v[index].rs=v[q].ls;
			v[q].ls=index;
			v[q].size=v[index].size;
			pushup(index);
			index=q;
		}
		int new_p(Type x)//创建新的节点 
		{
			v[++tot]={x,1,1,rand(),0,0};
			return tot;
		}
		void push(Type x,int &index)
		{
			if(!index)//新的节点 
			{
				index=new_p(x);
				return;
			}
			if(x==v[index].data)//有重复的 
			{
				v[index].t++;
                pushup(index);
				return;
			}
			if(x<v[index].data)
			{
				push(x,v[index].ls);
				if(v[index].ran<v[v[index].ls].ran)
					zig(index);
			}
			else
			{
				push(x,v[index].rs);
				if(v[index].ran<v[v[index].rs].ran)
					zag(index);
			}
			pushup(index);//这里记得加up(),不然size对不上 
		}
		void pop(Type x,int &index)
		{
			if(!index)return;
			if(x==v[index].data)
			{
				if(v[index].t>1)v[index].t--;
				else if(!v[index].ls || !v[index].rs)
					index=v[index].ls+v[index].rs;
				else if(v[v[index].ls].ran>v[v[index].rs].ran)
					zig(index),pop(x,v[index].rs);
				else
					zag(index),pop(x,v[index].ls);
                pushup(index);
				return;
			}
			if(x<v[index].data) pop(x,v[index].ls);
			else pop(x,v[index].rs);
			pushup(index);
		}
		int prev_index(Type x)
		{
			int index=root;
			int ans=0;
			while(index)
			{
				if(v[index].data<x) ans=index,index=v[index].rs;
				else index=v[index].ls;
			}
			return ans;
		}
		int next_index(Type x)
		{
			int index=root;
			int ans=0;
			while(index)
			{
				if(v[index].data>x) ans=index,index=v[index].ls;
				else index=v[index].rs;
			}
			return ans;
		}
		int get_rank(Type x,int index)
		{
			if(!index)return 1;
			if(x==v[index].data)return v[v[index].ls].size+1;
			if(x<v[index].data)return get_rank(x,v[index].ls);
			else return get_rank(x,v[index].rs)+v[v[index].ls].size+v[index].t;
		}
		Type get_topk(int x,int index)
		{
			if(!index)return 0;
			if(x<=v[v[index].ls].size)return get_topk(x,v[index].ls);
			if(x<=v[v[index].ls].size+v[index].t)return v[index].data;
			return get_topk(x-v[v[index].ls].size-v[index].t,v[index].rs);
		}
	public:
		int size()
		{
			return v[root].size;
		}
		Type get_prev(int x)
		{
			return v[prev_index(x)].data;
		}
		Type get_next(int x)
		{
			return v[next_index(x)].data;
		}
		int get_rank(Type x)
		{
			return get_rank(x,root);
		}
		Type get_topk(int x)
		{
			return get_topk(x,root);
		}
		void push(Type x)
		{
			push(x,root);
		}
		void pop(Type x)
		{
			pop(x,root);
		}
};