3314 - 权值线段树

通过次数

9

提交次数

37

时间限制 : 1 秒
内存限制 : 128 MB

实现一个数据结构,来维护一些数,其中需要提供以下操作:
1.插入x数;
2.删除x数(若有多个相同的数,应只删除一个);
3.查询x数的排名(排名定义为比当前数小的数的个数+ 1 );
4.查询排名为x的数;
5.求x的前驱(前驱定义为小于x,且最大的数);
6.求x的后继(后继定义为大于x,且最小的数)。

输入

第一行输入n,表示操作的个数,下面n行每行有两个数 opt 和x,opt 表示操作的序号(1<=n<=10^5,|x|<=10^7)。

输出

输出对于操作每行输出一个数,表示对应查询的答案。

样例

输入

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

输出

106465
84185
492737