#include<cstdio>

#include<cstdlib>

const int inf  = ~0u>>;

#define L ch[x][0]

#define R ch[x][1]

#define KT (ch[ ch[rt][1] ][0])

const int maxn = ;

int lim;

struct SplayTree {

    int sz[maxn];

    int ch[maxn][];

    int pre[maxn];

    int rt,top;

    inline void up(int x){

        sz[x]  = cnt[x]  + sz[ L ] + sz[ R ];

    }

    inline void Rotate(int x,int f){

        int y=pre[x];

        ch[y][!f] = ch[x][f];

        pre[ ch[x][f] ] = y;

        pre[x] = pre[y];

        if(pre[x]) ch[ pre[y] ][ ch[pre[y]][] == y ] =x;

        ch[x][f] = y;

        pre[y] = x;

        up(y);

    }

    inline void Splay(int x,int goal){//将x旋转到goal的下面

        while(pre[x] != goal){

            if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][] == x);

            else   {

                int y=pre[x],z=pre[y];

                int f = (ch[z][]==y);

                if(ch[y][f] == x) Rotate(x,!f),Rotate(x,f);

                else Rotate(y,f),Rotate(x,f);

            }

        }

        up(x);

        if(goal==) rt=x;

    }

    inline void RTO(int k,int goal){//将第k位数旋转到goal的下面

        int x=rt;

        while(sz[ L ] != k-) {

            if(k < sz[ L ]+) x=L;

            else {

                k-=(sz[ L ]+);

                x = R;

            }

        }

        Splay(x,goal);

    }

    inline void vist(int x){

        if(x){

            printf("结点%2d : 左儿子  %2d   右儿子  %2d   val:%2d sz=%d  cnt:%d\n",x,L,R,val[x],sz[x],cnt[x]);

            vist(L);

            vist(R);

        }

    }

    void debug() {

        puts("");

        vist(rt);

        puts("");

    }

    inline void Newnode(int &x,int c,int f){

        x=++top;

        L = R = ;

        pre[x] = f;

        sz[x]=; cnt[x]=;

        val[x] = c;

    }

    inline void init(){

        ch[][]=ch[][]=pre[]=sz[]=;

        rt=top=; cnt[]=;

    }

    inline void Insert(int &x,int key,int f){

        if(!x) {

            Newnode(x,key,f);

            Splay(x,);//注意插入完成后splay

            return ;

        }

        if(key==val[x]){

            cnt[x]++;

            sz[x]++;

            Splay(x,);//注意插入完成后splay

            return ;

        }else if(key<val[x]) {

            Insert(L,key,x);

        } else {

            Insert(R,key,x);

        }

        up(x);

    }

    void Del_root(){//删除根节点

        int t=rt;

        if(ch[rt][]) {

            rt=ch[rt][];

            RTO(,);

            ch[rt][]=ch[t][];

            if(ch[rt][]) pre[ch[rt][]]=rt;

        }

        else rt=ch[rt][];

        pre[rt]=;

        up(rt);

    }

    void findpre(int x,int key,int &ans){//找前驱节点

        if(!x)  return ;

        if(val[x] <= key){

            ans=x;

            findpre(R,key,ans);

        } else

            findpre(L,key,ans);

    }

    void findsucc(int x,int key,int &ans){//找后继节点

        if(!x) return ;

        if(val[x]>=key) {

            ans=x;

            findsucc(L,key,ans);

        } else

            findsucc(R,key,ans);

    }

    inline int find_kth(int x,int k){ //第k小的数

        if(k<sz[L]+) {

            return find_kth(L,k);

        }else if(k > sz[ L ] + cnt[x] )

            return find_kth(R,k-sz[L]-cnt[x]);

        else{

            Splay(x,);

            return val[x];

        }

    }

    int find(int x,int key){

        if(!x) return ;

        else if(key < val[x])  return find(L,key);

        else if(key > val[x])  return find(R,key);

        else return x;

    }

    int getmin(int x){

        while(L) x=L;    return val[x];

    }

    int getmax(int x){

        while(R) x=R;   return val[x];

    }

    //确定key的排名

    int getrank(int x,int key,int cur){//cur:当前已知比要求元素（key）小的数的个数

        if(key == val[x])

            return sz[L] + cur + ;

        else if(key < val[x])

            getrank(L,key,cur);

        else

            getrank(R,key,cur+sz[L]+cnt[rt]);

    }

    int get_lt(int x,int key){//小于key的数的个数 lt:less than

        if(!x) return ;

        if(val[x]>=key) return get_lt(L,key);

        return cnt[x]+sz[L]+get_lt(R,key);

    }

    int get_mt(int x,int key){//大于key的数的个数 mt:more than

        if(!x) return ;

        if(val[x]<=key) return get_mt(R,key) ;

        return cnt[x]+sz[R]+get_mt(L,key);

    }

    void del(int &x,int f){//删除小于lim的所有的数所在的节点

        if(!x) return ;

        if(val[x]>=lim){

            del(L,x);

        } else {

            x=R;

            pre[x]=f;

            if(f==)  rt=x;

            del(x,f);

        }

        if(x)  up(x);

    }

    inline void update(){

        del(rt,);

    }

    int get_mt(int key) {

        return get_mt(rt,key);

    }

    int get_lt(int key) {

        return get_lt(rt,key);

    }

    void insert(int key) {

        Insert(rt,key,);

    }

    void Delete(int key) {

        int node=find(rt,key);

        Splay(node,);

        cnt[rt]--;

        if(!cnt[rt])Del_root();

    }

    int kth(int k) {

        return find_kth(rt,k);

    }

    int cnt[maxn];

    int val[maxn];

    int lim;

}spt;