Splay

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int rt, tot, fa[100005], sz[100005], val[100005], cnt[100005], ch[100005][2];//(左右)

bool get(int x) {return x == ch[fa[x]][1];}//返回左子树or右子树
void maintain(int x) {sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];} //更新子树大小
void clear(int x) {ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;}

void rotate(int x) //旋转
{
    int y = fa[x], z = fa[y], chx = get(x);
    ch[y][chx] = ch[x][chx ^ 1];
    if(ch[x][chx ^ 1]) fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    fa[x] = z;
    if(z) ch[z][y == ch[z][1]] = x;
    maintain(y);
    maintain(x);
}

void splay(int x) //splay操作
{
    for (int f = fa[x]; f = fa[x]; rotate(x))
    {
        if(!f) break;//没父亲了，成为根，退出
        if (fa[f]) //如果祖先有祖先
        {
            if(get(x) == get(f)) rotate(f); // 同侧,zig-zig;
            else rotate(x); //异侧，zig-zag
        }
    }
    rt = x;
}

void insert(int k)
{
    if(!rt) //空树，插入根，退出
    {
        val[++tot] = k;
        cnt[tot]++;
        rt = tot;
        maintain(rt);
        return;
    }

    int cur = rt, f = 0;
    while(1)
    {
        if(val[cur] == k) //找到值了，增加节点大小，更新节点和父亲的信息，进行splay操作
        {
            cnt[cur]++;
            maintain(cur);
            maintain(f);
            splay(cur);
            break;
        }

        f = cur;
        cur = ch[cur][val[cur] < k];

        if(!cur) //找到空节点，插入
        {
            val[++tot] = k;
            cnt[tot]++;
            fa[tot] = f;
            ch[f][val[f] < k] = tot;
            maintain(tot);
            maintain(f);
            splay(tot);
            break;
        }
    }
}

int rk(int k) //x的排名
{
    int res = 0, cur = rt;
    while(1)
    {
        if(k < val[cur]) cur = ch[cur][0];//小于该点权值，向左子树查询
        else 
        {
            res += sz[ch[cur][0]];//大于等于该点权，加上左子树
            if(!cur) return res + 1;//若无右子树，加上自身后直接返回
            if(k == val[cur]) {
                splay(cur);//找到后要进行splay操作，是为了均摊复杂度
                return res + 1;
            }
            res += cnt[cur];//加上该点值的个数
            cur = ch[cur][1];//进入右子树
        }
    }
}

int kth(int k) //第k大的数
{
    int cur = rt;
    while(1)
    {
        if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; 
        //如果左子树非空且剩余排名 k 不大于左子树的大小 size，那么向左子树查找
        else
        {
            k -= cnt[cur] + sz[ch[cur][0]]; //剩余排名减去左子树大小和根大小
            if (k <= 0) {//如果小于等于零了，说明找到了
                splay(cur);
                return val[cur];
            }
            cur = ch[cur][1];
        }
    }
}

int pre() //前驱
//转化为：将 x 插入，前驱即为 x 的左子树中最右边的节点，最后将 x 删除即可。
{
    int cur = ch[rt][0];
    if (!cur) return cur;
    while (ch[cur][1]) cur = ch[cur][1];
    splay(cur);
    return cur;
}

int nxt() //后继
//同前驱
{
    int cur = ch[rt][1];
    if (!cur) return cur;
    while (ch[cur][0]) cur = ch[cur][0];
    splay(cur);
    return cur;
}

void del(int x) //删除
{
    rk(x);//将x旋转到根节点
    if (cnt[rt] > 1) //若根的大小大于一，减一后退出即可
    {
        cnt[rt]--;
        maintain(rt);
        return;
    }

    if (!ch[rt][0] && !ch[rt][1]) //左右子树都没了，删空
    {
        clear(rt);
        rt = 0;
        return;
    }

    if (!ch[rt][0]) //对于左或右子树空的操作都是很简单的
    {
        int cur = rt;
        rt = ch[rt][1];
        fa[rt] = 0;
        clear(cur);
        return;
    }

    if (!ch[rt][1]) 
    {
        int cur = rt;
        rt = ch[rt][0];
        fa[rt] = 0;
        clear(cur);
        return;
    }

    int cur = rt, x = pre();//将前驱splay为根节点
    fa[ch[cur][1]] = x;//将原根右子树接上
    ch[x][1] = ch[cur][1];
    clear(cur);
    maintain(rt);
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, t, x;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> t >> x;
        if(t == 1) insert(x);
        else if(t == 2) del(x);
        else if(t == 3) cout << rk(x) << '\n';
        else if(t == 4) cout << kth(x) << '\n';
        else if(t == 5) insert(x), cout << val[pre()] << '\n',del(x);
        else insert(x), cout << val[nxt()] << '\n', del(x);
    }

}