#include <fstream>

using namespace std;
ifstream cin ("heapuri.in");
ofstream cout ("heapuri.out");
int heap[200010],nr,k;
int n;
int poz_heap[200010];
int poz_frecv[200010];
void climb (int poz)
{
      while(3>2)
      {
            if(poz>1 && heap[poz/2]>heap[poz])
            {
                  swap(heap[poz],heap[poz/2]);
                  swap(poz_heap[poz],poz_heap[poz/2]);
                  poz_frecv[poz_heap[poz]]=poz;
                  poz_frecv[poz_heap[poz/2]]=poz/2;
                  poz/=2;
            }
            else break;
      }
}
void down (int poz)
{
      int fiu=0;
      while(3>2)
      {
            if(poz*2<=nr) fiu=poz*2;
            if(poz*2+1<=nr && heap[poz*2+1]<heap[fiu]) fiu++;
            if( fiu && heap[fiu]<heap[poz] )
            {
                  swap(heap[poz],heap[fiu]);
                  swap(poz_heap[poz],poz_heap[fiu]);
                  poz_frecv[poz_heap[poz]]=poz;
                  poz_frecv[poz_heap[fiu]]=fiu;
                  poz=fiu;
            }
            else break;
      }
}
void read ()
{ int cod,x;
      cin>>n;
      for(int i=1;i<=n;i++)
      {
            cin>>cod; if(cod!=3) cin>>x;
            if(cod==1)
            {     ++k;
                  heap[++nr]=x;
                  poz_heap[nr]=k;
                  poz_frecv[k]=nr;
                  climb(nr);
            }
            else if(cod==2)
            {
                 heap[poz_frecv[x]]=heap[nr];
                 poz_heap[poz_frecv[x]]=poz_heap[nr];
                 poz_frecv[poz_heap[nr]]=poz_frecv[x];
                 nr--;
                 down(poz_frecv[x]);
            }
            else cout<<heap[1]<<"\n";
      }
}
int main()
{
    read();
    cin.close();
    cout.close();
    return 0;
}