/*
treap = tree+heap(相对其他树操作比较少)
红黑树(代码太长)
splay(比较难)
AVL

1 binary search tree BST 二叉搜索树
   val in root.left<root.val<val in root.right
中序遍历 是从小到大的
左中右
BST就是动态维护一个有序序列/有序集合

            5
           / \
          4   8
         /   / \
        2   6   9
       / \   \ 
      1   3   7

1 插入操作
1.1插入已有的值 以3为例
        2   
       / \    
      1   3
           \
            3
            3.cnt++
1.2插入没有的值 以10为例
            5
           / \
          4   8
         /   / \
        2   6   9
       / \   \   \
      1   3   7   10

2删除操作
2.1删除中间节点(把中间节点转为叶子节点)
2.2删除叶子节点(直接删)

3找前驱后继
3.1找前驱(前驱:中序遍历中在当前节点的前一个位置的节点)
3.1.1 如果当前节点root存在左子树  
      左子树root.left中的最大值(从root.left一直往右走)就是root的前驱
      left = root.left
      while(left.right) left = left.right
3.1.2 如果当前节点root不存在左子树
      就找父节点fa
      如果父节点是右爸爸 root=fa.left 那么root.val<fa.val 所以父节点fa不是root的前驱
          则继续看右爸爸的爸爸 fa.fa,直到出现左爸爸(当前节点是父节点右儿子)时,
          说明该父节点比当前节点以及当前节点的所有儿子都小
  (比答案小)o   o(比答案以及答案的所有子节点都大,不满足小于p)
             \ /
              o(答案,小于p的节点中的最大值)
               \ 
                o(第一个出现左爸爸的节点)
               /
              o(出发点p,只有右爸爸)
3.2找后继(后继:中序遍历中在当前节点的后一个位置的节点)

4 找最大/最小 end() begin()

1->4就是set()

5 求某个值的排名

6 求排名是k的数是哪个

7 比某个数小的最大值/比某个数大的最小值 

treap 让BST尽量随机(使得高度接近logn)

node
{
    int l,r;左儿子编号 右儿子编号
    int key,val;排序序号(BST,有序) 优先级(大根堆heap里的)
}tr[N]
root.val >= root.left.val 
root.val >= root.right.val
val取随机,则树的结构就随机(高度的平均就接近logn)

加两个哨兵
-∞  +∞ 处理边界
1 插入
    先递归到插进去再说(回溯时类似堆的回溯,如果当前p.val>fa.val 交换p和fa的位置)
    实现过程->左旋 & 右旋
     x               y
    / \  右旋zig    / \
   y   tt   ->     hh  x
  / \      <-         / \
 hh  z   左旋zag     z   tt
 hh,tt分别在整个序列的最前和最后 在旋转前后没有变化
 同时 中序遍历(递增序列)的结构在旋转前后都是 hh y z x tt 
     p               q
    / \  右旋zig    / \
   q   c   ->      a   p
  / \      <-         / \
 a   b   左旋zag     b   c
2 删除
    类似堆 把当前节点x交换到tt的位置,然后删除
    只不过在这里的操作是通过右旋
    可以发现每次右旋x就到了x.right的位置
    所以我们可以一直右旋直到x变为叶子节点,然后删除

*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 1e8;

int n;
struct Node
{
    int l, r;
    int key, val;//节点键值 || 权值
    int cnt, size;//这个数出现次数 || 每个(节点)子树里数的个数
}tr[N];

int root, idx;

void pushup(int p)//儿子信息更新父节点信息
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
    //左儿子树 数个数+ 右儿子树 数个数+ 当前节点数出现次数(重复次数)
}

int get_node(int key)
{
    tr[++idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;//默认创建时都是叶子节点
    return idx;
}

/*         b挂x           交换pq 
     x(p)            y(q)         y(p)
    / \  右旋zig    / \           / \
   y(q)c   ->      a   x(p) ->   a   x(tr[p].r)
  / \                 / \           / \
 a   b               b   c         b   c
*/
void zig(int &p)//右旋  p指针指向的根节点
{
    int q = tr[p].l;//先把p的左儿子q存下来
    tr[p].l = tr[q].r;//b从q的右儿子变为p的左儿子
    tr[q].r = p;//最终q的右儿子是p指向的x
    p = q;//p从指向原来根节点x变为指向新根节点q
    pushup(tr[p].r),pushup(p);//先更新 右子树(x bc) 再更新根节点y
}
/*                交换pq          b挂x
             y(p)          y(q)            x(p)
             / \          / \             / \
    (tr[p].l)x  c        x(p)c           a   y(q)
           / \     <-   / \      <-         / \
          a   b        a   b   左旋zag     b   c
*/
void zag(int &p)
{
    int q = tr[p].r;//先把p的右儿子y(q)存下来
    tr[p].r = tr[q].l;//b挂x(p)
    tr[q].l = p;//p挂y的左儿子
    p=q;//p维护指向根节点
    pushup(tr[p].l),pushup(p);
}

void build()
{
    get_node(-INF),get_node(INF);
    root = 1,tr[1].r = 2;//根节点1号点,1号点的右儿子2号点
    //build的时候不要漏了维护树的结构
    pushup(root);
    if (tr[1].val < tr[2].val) zag(root);
}

void insert(int &p,int key)
{
    if(!p) p = get_node(key);//如果到达叶子节点fa 并进一步递归tr[fa].l or tr[fa].r == 空 新增一个key叶子节点
    else if(tr[p].key == key) tr[p].cnt++;//如果插入已有的值 cnt++
    else if(tr[p].key>key) //插入新的值 判断插入左子树还是右子树 直到叶子节点
    {//如果要插入的key比p的key小 递归tr[p]的左子树tr[p].l
        insert(tr[p].l,key);
        if(tr[tr[p].l].val > tr[p].val) zig(p);//如果左子树val大于root.val 就换上来
    }
    //维护val是根节点root.val > 子树 root.l.val or root.r.val 
    else
    {//如果要插入的key比p的key大 递归tr[p]的右子树tr[p].r
        insert(tr[p].r,key);
        if(tr[tr[p].r].val > tr[p].val) zag(p);//如果右子树val大于root.val 就换上来
    }
    pushup(p);
}

void remove(int &p,int key)
{
    if(!p) return;//如果删除的值不存在
    if(tr[p].key == key)//如果有值
    {
        if(tr[p].cnt>1) tr[p].cnt--;//如果cnt>1 cnt--
        else if(tr[p].l || tr[p].r)//否则判断是否叶子节点 
        {//如果不是叶子节点
            if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)//右旋把p放到右子树 递归到叶子节点删除
            {//如果没有右子树 肯定可以右旋 || 左子树的.val > 右子树的val
                zig(p);
                remove(tr[p].r,key);
            }
            else//否则左旋把p放到左子树 递归到叶子节点删除
            {
                zag(p);
                remove(tr[p].l,key);
            }
        }
        else p=0;//如果是叶子节点 直接删除
    }
    else if(tr[p].key > key) remove(tr[p].l,key);//如果 要删除的中序顺序key>当前节点p的tr[p].key 去p左子树删
    else remove(tr[p].r,key);
    pushup(p);
}

int get_rank_by_key(int p,int key)//通过数值找排名  传p而不是传&p
{
    if(!p) return 0;//如果p不存在 返回0
    if(tr[p].key==key) return tr[tr[p].l].size+1;//如果key和当前节点key相等 排名=左子树数的大小+1(当前节点)
    if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);//漏了return
    //说明要找的key比当前节点小 去当前节点左子树找
    return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r,key);
    //去右边找返回的是右边子树的排名,所以还得加上根节点root数的个数以及根节点左子树总数root.l.size
}

int get_key_by_rank(int p,int rank)//通过排名找数值 传p而不是传&p
{
    if(!p) return INF;//p不存在 则返回不可能存在的排名
    if(tr[tr[p].l].size >=rank) return get_key_by_rank(tr[p].l,rank);//如果左子树数的个数>rank,则去左子树找
    if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].key;//左子树+当前节点个数>=rank,则就是当前节点
    //左子树+当前节点个数<rank,则递归右子树,同时往下传的rank-左子树-当前节点个数
    return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);//-tr[p].cnt
}

int get_prev(int p,int key)//找到严格小于key的数中的最大数 传p而不是传&p
{
    if(!p)return -INF;
    if(tr[p].key>=key) return get_prev(tr[p].l,key);//当前这个数>=key 则要找的数在当前节点的左子树里
    return max(tr[p].key, get_prev(tr[p].r, key));
    // if(tr[p].key<key) //当前节点<key max(当前节点(无右子树) || 当前节点的右子树中的最大值(有右子树))
    // {
    //     if(tr[p].r) return get_prev(tr[p].r,key); //错了 有右子树 但右子树的key不一定比要找的key小
    //     return tr[p].key;
    // }
}

int get_next(int p,int key)//找到严格大于key的数中的最小数 传p而不是传&p
{
    if (!p) return INF;
    if (tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
    build();
    scanf("%d",&n);
    while(n--)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1) insert(root,x);
        else if (op == 2) remove(root,x);
        else if (op == 3) printf("%d\n", get_rank_by_key(root, x) - 1);
        else if (op == 4) printf("%d\n", get_key_by_rank(root, x + 1));
        else if (op == 5) printf("%d\n", get_prev(root, x));
        else printf("%d\n", get_next(root, x));
    }
    return 0;
}