#ifndef TREAP
#define TREAP
template<typename T>
class treap{
    private:
        struct node{
            T data;
            unsigned fix;
            int size;
            node *ch[2];
            node(const T&d):data(d),size(1){}
            node():size(0){ch[0]=ch[1]=this;}
        }*nil,*root;
        unsigned x;
        inline unsigned ran(){
            return x=x*0xdefaced+1;
        }
        inline void rotate(node *&a,bool d){
            node *b=a;
            a=a->ch[!d];
            a->size=b->size;
            b->ch[!d]=a->ch[d];
            a->ch[d]=b;
            b->size=b->ch[0]->size+b->ch[1]->size+1;
        }
        void insert(node *&o,const T &data){
            if(!o->size){
                o=new node(data),o->fix=ran();
                o->ch[0]=o->ch[1]=nil;
            }else{
                o->size++;
                bool d=o->data<data;
                insert(o->ch[d],data);
                if(o->ch[d]->fix>o->fix)rotate(o,!d);
            }
        }
        bool success_erase(node *&o){
            if(!o->ch[0]->size||!o->ch[1]->size){
                node *t=o;
                o=o->ch[0]->size?o->ch[0]:o->ch[1];
                delete t;
            }else{
                o->size--;
                bool d=o->ch[0]->fix>o->ch[1]->fix;
                rotate(o,d);
                success_erase(o->ch[d]);
            }
            return 1;
        }
        bool erase(node *&o,const T &data){
            if(!o->size)return 0;
            if(o->data==data)return success_erase(o);
            if(erase(o->ch[o->data<data],data)){
                o->size--;return 1;
            }else return 0;
        }
        void clear(node *&o){
            if(o->size)clear(o->ch[0]),clear(o->ch[1]),delete o;
        }
    public:
        treap(unsigned s=20150119):nil(new node),root(nil),x(s){}
        ~treap(){clear(root),delete nil;}
        inline void clear(){clear(root),root=nil;}
        inline void insert(const T &data){
            insert(root,data);
        }
        inline bool erase(const T &data){
            return erase(root,data);
        }
        inline bool find(const T&data){
            for(node *o=root;o->size;)
            if(o->data==data)return 1;
            else o=o->ch[o->data<data];
            return 0;
        }
        inline int rank(const T&data){
            int cnt=0;
            for(node *o=root;o->size;)
            if(o->data<data)cnt+=o->ch[0]->size+1,o=o->ch[1];
            else o=o->ch[0];
            return cnt;
        }
        inline const T&kth(int k){
            for(node *o=root;;)
            if(k<=o->ch[0]->size)o=o->ch[0];
            else if(k==o->ch[0]->size+1)return o->data;
            else k-=o->ch[0]->size+1,o=o->ch[1];
        }
        inline const T&operator[](int k){
            return kth(k);
        }
        inline const T&preorder(const T&data){
            node *x=root,*y=0;
            while(x->size)
            if(x->data<data)y=x,x=x->ch[1];
            else x=x->ch[0];
            if(y)return y->data;
            return data;
        }
        inline const T&successor(const T&data){
            node *x=root,*y=0;
            while(x->size)
            if(data<x->data)y=x,x=x->ch[0];
            else x=x->ch[1];
            if(y)return y->data;
            return data;
        }
        inline int size(){return root->size;}
};
#endif