Splay

struct Splay{   
    #define ls p[u].son[0]
    #define rs p[u].son[1]
    #define maxn 100000

    int root, cnt;
    struct Node{
        int val, fa, size, sum;
        int son[2]; 
    }p[maxn];
    
    inline void destroy(int u){
        p[u].val = ls = rs = p[u].fa = p[u].sum = p[u].size = 0;
    }

    inline int identify(int u){
        return p[p[u].fa].son[1] == u;
    }

    inline void update(int u){
        if(u)   p[u].sum = p[ls].sum + p[rs].sum + p[u].size;
    }

    void rotate(int u){
        int f = p[u].fa,  gf = p[f].fa,  sta = identify(u),  sta_f = identify(f);
        p[f].son[sta] = p[u].son[sta ^ 1];
        p[p[f].son[sta]].fa = f;
        p[u].son[sta^1] = f,  p[f].fa = u,  p[u].fa = gf;
        p[gf].son[sta_f] = u;
        update(f);
    }

    void splay(int u, int goal){
        for(int f; (f = p[u].fa) && (f != goal); rotate(u))
            if(p[f].fa != goal)  rotate(identify(u) == identify(f) ? f : u);
        if(!goal)  root = u;
        update(u);
    }

    void insert(int u){
        if(!root){
            p[++cnt].val = u;
            p[cnt].size = p[cnt].sum = 1;
            root = cnt;
            return ;
        }
        int now = root,  f = 0;
        while(true){
            if(u == p[now].val){
                ++p[now].size;
                splay(now, 0);
                return ;
            }
            f = now,  now = p[now].son[p[now].val < u];
            if(!now){
                p[++cnt].val = u;
                p[cnt].size = p[cnt].sum = 1;
                p[cnt].fa = f,  p[f].son[p[f].val < u] = cnt;
                ++p[f].sum;
                splay(cnt, 0);
                return ;
            }
        }
    }

    int find_num(int u){
        int now = root;
        while(true){
            if(p[now].son[0] && u <= p[p[now].son[0]].sum)
                now = p[now].son[0];
            else{
                int temp = p[p[now].son[0]].sum + p[now].size;
                if(u <= temp)   return p[now].val;
                now = p[now].son[1],  u -= temp;
            }
        }
    }

    int find_rank(int u){
        int now = root,  rank = 0;
        while(true){
            if(u < p[now].val)    now = p[now].son[0];
            else{
                rank += p[p[now].son[0]].sum;
                if(u == p[now].val){
                    splay(now, 0);
                    return rank + 1;
                }
                rank += p[now].size,  now = p[now].son[1];
            }
        }
    }

    int find_pre(){
        int now = p[root].son[0];
        while(p[now].son[1])    now = p[now].son[1];
        return now;
    }

    int find_suffix(){
        int now = p[root].son[1];
        while(p[now].son[0])
            now = p[now].son[0];
            return now;
    }

    void delete_val(int u){
        find_rank(u);
        if(p[root].size > 1){
            --p[root].size,  --p[root].sum;
            return ;
        }
        if(!p[root].son[0] && !p[root].son[1]){
            destroy(root),  root = 0;
            return ;
        }
        int old_root = root;
        if(!p[root].son[0]){
            root = p[root].son[1];
            p[root].fa = 0;
            destroy(old_root);
            return ;
        }
            if(!p[root].son[1]){
            root = p[root].son[0];
            p[root].fa = 0;
            destroy(old_root);
            return ;
        }
        int left_max = find_pre();
        splay(left_max, 0);
        p[root].son[1] = p[old_root].son[1];
        p[p[old_root].son[1]].fa = root;
        destroy(old_root);
        update(root);
    }
};