#include <iostream>
#include<fstream>
#include<algorithm>

using namespace std;

ifstream f("heapuri.in");
ofstream g("heapuri.out");
int heap[2000005],poz[2000005],a[2000005],nr,k;
int i,x,tip;

void urca(int pozi)
{
    while(pozi>1&& a[heap[pozi]]<a[heap[pozi/2]])
    {
        swap(heap[pozi],heap[pozi/2]);
        poz[heap[pozi]]=pozi;
        poz[heap[pozi/2]]=pozi/2;
        pozi/=2;

    }
}

void coboara(int pozi)
{
 {
    int poz1=0;

    while(pozi!=poz1) {
        poz1=pozi;

        if(2*poz1<=k && a[heap[pozi]]>a[heap[2*pozi]])
            pozi=2*poz1;
        if(2*poz1+1<=k && a[heap[pozi]]>a[heap[2*poz1+1]])
            pozi=2*poz1+1;

        swap(heap[pozi],heap[poz1]);
        poz[heap[pozi]]=pozi;
        poz[heap[poz1]]=poz1;

        }
}}

int main()
{int n=0;
    f>>nr;
    for(i=1;i<=nr;i++)
    {
        f>>tip;
        if(tip==1)
        {
            f>>x;
        a[++n]=x;
        heap[++k]=n;
        poz[n]=k;
        urca(k);
        }
        else if(tip==2)
        {
            f>>x;
            a[x]=a[heap[k--]];
            urca(poz[x]);
            coboara(poz[x]);
            poz[heap[1]]=1;
        }
        else
        {
            g<<a[heap[1]]<<'\n';
        }
    }
    return 0;
}