#include <fstream>

using namespace std;

 ifstream x ("heapuri.in");
 ofstream y ("heapuri.out");

 struct heap
 {
     int data;
     int cronos;
     heap *parent;
     heap *left;
     heap *right;
     heap *predecesor;
     heap *succesor;
 };

 int N;
 heap *root,*Q;
 heap *current;
 heap *temp;
 heap *auxiliar;

 void interschimba(int &a, int &b)
 {
     int aux;

     aux=a;
     a=b;
     b=aux;
 }

 void wreck(heap *auxiliar)
 {
     heap *black;
     heap *yellow;

     if(auxiliar->left)
        black=auxiliar->left;
     else
        black=NULL;

     if(auxiliar->right)
        yellow=auxiliar->right;
     else
        yellow=NULL;

     if(black && yellow)
        if(black->data<yellow->data)
        {
            interschimba(black->data,auxiliar->data);
            interschimba(black->cronos,auxiliar->cronos);

            wreck(black);
        }
        else
        {
            interschimba(yellow->data,auxiliar->data);
            interschimba(yellow->cronos,auxiliar->cronos);

            wreck(yellow);
        }
     else
        if(black)
        {
            interschimba(black->data,auxiliar->data);
            interschimba(black->cronos,auxiliar->cronos);

            wreck(black);
        }
        else
           if(yellow)
           {
               interschimba(yellow->data,auxiliar->data);
               interschimba(yellow->cronos,auxiliar->cronos);

               wreck(yellow);
           }
 }

int main()
{
    int i;

    x>>N;

    int a,b;
    int k=0;

    for(i=1;i<=N;i++)
    {
        x>>a;

        if(a==1)
        {
            x>>b;

            if(root==NULL)
            {
                root=new heap();

                root->data=b;
                root->cronos=k+1;
                root->parent=NULL;
                root->left=NULL;
                root->right=NULL;
                root->predecesor=NULL;
                root->succesor=NULL;
                current=root;
                temp=root;

                Q=root;
            }
            else
            {
                k++;

                current=new heap();

                current->data=b;
                current->cronos=k+1;
                current->parent=Q;
                current->left=NULL;
                current->right=NULL;
                current->predecesor=temp;
                temp->succesor=current;
                current->succesor=NULL;

                temp=current;

                if(k%2==1)
                   Q->left=current;
                else
                   Q->right=current;

                if(k%2==0)
                   Q=Q->succesor;
            }

            while(current->parent)
               if(current->data<current->parent->data)
               {
                   interschimba(current->data,current->parent->data);
                   interschimba(current->cronos,current->parent->cronos);

                   current=current->parent;
               }
               else
                  break;
        }
        else
           if(a==2)
           {
               x>>b;

               auxiliar=root;

               while(auxiliar)
               {
                   if(auxiliar->cronos==b)
                   {
                       auxiliar->data=1000000001;
                       wreck(auxiliar);
                       break;
                   }

                   auxiliar=auxiliar->succesor;
               }
           }
           else
              y<<root->data<<'\n';
/*
        auxiliar=root;

        while(auxiliar)
        {
            y<<auxiliar->data<<' ';

            auxiliar=auxiliar->succesor;
        }
        y<<'\n';

        auxiliar=root;

        while(auxiliar)
        {
            y<<auxiliar->cronos<<' ';

            auxiliar=auxiliar->succesor;
        }
        y<<'\n';

        y<<'\n';
*/
    }

    return 0;
}