#include<fstream>
#define Y return
#define L if
#define E else
#define B n->l
#define C n->r
using namespace std;template<typename T>class A{private:struct N{T v;int h;N*l,*r;N(N*n,int H){v=0;h=H;l=r=n;}};N*R,*D;N*i(N*n,T&v){L(n==D){n=new N(D,0);n->v=v;Y n;}L(v<n->v)B=i(B,v);E L(v>n->v)C=i(C,v);Y b(n);}int w(N*n,T&v){L(n==D)Y 0;E L(v==n->v)Y 1;E L(v<n->v)Y w(B,v);E Y w(C,v);}N*e(N*n,T&v){L(n==D)Y D;L(n->v==v){L(B==D||C==D){N*p=(B==D?C:B);delete n;Y p;}E{N*p;p=B;while(p->r!=D)p=p->r;n->v=p->v;B=e(B,p->v);}}E L(v<n->v)B=e(B,v);E C=e(C,v);Y b(n);}void z(N*n){n->h=1+max(B->h,C->h);}N*x(N*n){N*p=C;C=p->l;p->l=n;z(n);z(p);Y p;}N*y(N*n){N*p=B;B=p->r;p->r=n;z(n);z(p);Y p;}N*b(N*n){z(n);L(B->h+1<C->h){L(C->l->h>C->r->h)C=y(C);n=x(n);}E L(C->h+1<B->h){L(B->r->h>B->l->h)B=x(B);n=y(n);}Y n;}public:A(){D=new N(D,-1);R=D;}void i(T&v){R=i(R,v);}int w(T&v){Y w(R,v);}void e(T&v){R=e(R,v);}};int main(){int q,x,T;A<int>V;ifstream I("hashuri.in");ofstream O("hashuri.out");I>>T;while(T--){I>>q>>x;switch(q){case 1:V.i(x);break;case 2:V.e(x);break;case 3:O<<V.w(x)<<'\n';}}Y 0;}