#include<stdio.h>
#include<iostream>
#define dim 200005
using namespace std;

FILE *f=fopen("heapuri.in","r"), *g=fopen("heapuri.out","w");


struct nod
{int inf; nod * st; nod * dr;};

nod *p, *cap=NULL;
int n,nr,i,cod,j,v[dim];

void add(nod *&cap, int nr)
{
 if(!cap) {cap=new nod; cap->inf=nr; cap->st=NULL; cap->dr=NULL;}
 
 else
 {if(nr<cap->inf) 
	{if(cap->st==NULL) {p=new nod; p->inf=nr; cap->st=p; p->st=p->dr=NULL;}
	 else add(cap->st,nr);}
 else
	{if(cap->dr==NULL) {p=new nod; p->inf=nr; cap->dr=p; p->st=p->dr=NULL;}
	else add(cap->dr,nr);}
 }}
	


int out(nod *&cap, int nr)
{nod *p, *r,*q;
 if(cap->inf==nr) 
  {p=cap->st; q=cap->dr;
   if(p!=NULL)
  {delete cap; cap=p;
	while(p->dr!=NULL) p=p->dr;
    p->dr=q;
  }
  else cap=q;}

 else if(cap->inf>nr)
  {if(cap->st->inf==nr) 
    {p=cap->st->st; q=cap->st->dr;
       if(p) 
	     {r=cap->st; cap->st=p; delete r;
	      while(p->dr!=NULL)
	       p=p->dr;
		 
          p->dr=q;
	     }
	else {r=cap->st; cap->st=q; delete r;}}
   
   else out(cap->st,nr);}
  
  
 else if(cap->inf<nr)
  {if(cap->dr->inf==nr)
   {p=cap->dr->st; q=cap->dr->dr;
     if(p)
	 {r=cap->dr; cap->dr=p; delete r;
	   while(p->dr!=NULL)
		p=p->dr;
	 
	    p->dr=q;
     }
   else {r=cap->dr; cap->dr=q; delete r;}}
   
   else out(cap->dr,nr);
  }
}

void stanga()
{nod *p;
p=cap;
	while(p->st!=NULL)
  p=p->st;
 fprintf(g,"%d\n",p->inf);}

int main()
{
 
 fscanf(f,"%d",&n);
  for(i=1;i<=n;i++)
{fscanf(f,"%hd",&cod);
  if(cod!=3)
  {fscanf(f,"%d",&nr);
    if(cod==1) {add(cap,nr); j++; v[j]=nr;}
	else if(cod==2) out(cap,v[nr]);
	//srd(cap);
  }
  else if(cod==3) stanga();//fprintf(g,"%d\n",cap->inf);
}
 
 
fclose(f);
fclose(g);
return 0;
}