#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <random>
using namespace std;
const int N = 1e5 + 10;
struct node
{
int l, r; //左右儿子节点
int val, key;
int size;
}fhq[N]; //范浩强树起名fhq很合理(
int cnt, root;
//创建新的节点并且返回编号
inline int newnode(int val)
{
fhq[++cnt].val = val;
fhq[cnt].key = rand();
fhq[cnt].size = 1;
return cnt;
}
inline void pushup(int now)
{
fhq[now].size = fhq[fhq[now].l].size + fhq[fhq[now].r].size + 1;
return;
}
//分裂操作
//根据val 将一棵树分裂成x树和y树,并且x树小于y树
inline void split(int now, int val, int &x, int &y)
{
if (!now) x = y = 0; //如果分裂的树是空的 那么这俩树都是空的
else
{
if (fhq[now].val <= val)
{
x = now;
split(fhq[now].r, val, fhq[now].r, y);
}
else
{
y = now;
split(fhq[now].l, val, x, fhq[now].l);
}
pushup(now); //最后更新一下现在节点的状况
}
return;
}
// 注意x树是默认小于y树的
inline int merge(int x, int y)
{
//如果x和y树有一个是空的就返回二者和就行了
if (!x || !y) return x + y;
//key值根据大根堆,所以y要在x的下面
//但是y的值大于x,根据二叉树的性质要在x的右边
if (fhq[x].key > fhq[y].key)
{
fhq[x].r = merge(fhq[x].r, y);
pushup(x);
return x;
}
else
{
fhq[y].l = merge(x, fhq[y].l);
pushup(y);
return y;
}
}
int x, y, z;
//插入操作
//1.根据我们要插入的val的值将目前的树分为x和y树
//2.再将构建的节点val和x合并之后在和y合并
inline void insert(int val)
{
split(root, val, x, y);
root = merge(merge(x, newnode(val)), y);
return;
}
//删除操作
//1.将整棵树先根据val值分为x和z
//那么x树肯定就是小于z的了, 并且x树里面的所有值都是<= val
//2.将x树根据val分为x和y
//那么x里面的值 <= val - 1,而y树的根节点就是 val了
//3.y变为儿子的合并的树
//4.合并x, y, z
inline void delet_one(int val)
{
split(root, val, x, z);
split(x, val - 1, x, y);
y = merge(fhq[y].l, fhq[y].r);
root = merge(merge(x, y), z);
return;
}
//删除全部相同元素
//根据val将树分为x和z
//将x树根据val - 1再
inline void delet_all(int val)
{
split(root, val, x, z);
split(x, val - 1, x, y);
root = merge(x, z);
return;
}
//根据值找排名
//首先根据val - 1分为 x和y这样 x里的都是 <= val - 1
//然后根据x的size + 1就行了
inline void getrank(int val)
{
split(root, val - 1, x, y);
int res = fhq[x].size + 1;
root = merge(x, y);
cout << res << endl;
}
//根据排名找值
inline void getnum(int rank)
{
int now = root;
while (now)
{
if (fhq[fhq[now].l].size + 1 == rank) break; //如果now是目标的值
else if (fhq[fhq[now].l].size >= rank) now = fhq[now].l; // 如果目标值在左子树上
else//目标在右子树上(记得减rank值)
{
rank -= fhq[fhq[now].l].size + 1;
now = fhq[now].r;
}
}
cout << fhq[now].val << endl;
return;
}
//找val的前驱
//根据val - 1分为x树和y树
//只需在x树中找到最右边的值即可
inline void pre(int val)
{
split(root, val - 1, x, y);
int now = x;
while (fhq[now].r) now = fhq[now].r;
cout << fhq[now].val << endl;
//int res = fhq[get_num_by_rank(x, fhq[x].size)].val;
root = merge(x, y);
//cout << res << endl;
return;
}
//找val的后继
//与找前驱类似,找y树最左边
inline void back(int val)
{
split(root, val, x, y);
int now = y;
while (fhq[now].l) now = fhq[now].l;
cout << fhq[now].val << endl;
// int res = fhq[get_num_by_rank(y, 1)].val;
root = merge(x, y);
// cout << res << endl;
return;
}
int t;
int n;
inline void solve()
{
scanf("%d", &n);
int op, x;
while (n--)
{
scanf("%d%d", &op, &x);
if (op == 1)
{
insert(x);
}
else if (op == 2)
{
delet_one(x);
}
else if (op == 3)
{
getrank(x);
}
else if (op == 4)
{
getnum(x);
}
else if (op == 5)
{
pre(x);
}
else
{
back(x);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
t = 1;
while (t--)
{
solve();
}
return 0;
}