#include <bits/stdc++.h>

using namespace std;

ifstream f("heapuri.in");
ofstream g("heapuri.out");

int q,v[200005],h,poz[200005],cnt;
map<int,int> M;
void SiftUp(int i)
{
    if(i>1)
    {
        if(v[i]<v[i/2])
            swap(M[v[i]],M[v[i/2]]),swap(v[i],v[i/2]),SiftUp(i/2);
    }
}
void SiftDown(int i)
{
    int k=2*i;
    if(k<=h)
    {
        if(k+1<=h&&v[k+1]<v[k])
            k++;
        if(v[i]>v[k])
            swap(M[v[i]],M[v[k]]),swap(v[i],v[k]),SiftDown(k);
    }
}
int main()
{
    f>>q;
    while(q--)
    {
        int cer,x;
        f>>cer;
        assert(cer==1||cer==2||cer==3);
        if(cer==1)
        {
            f>>x;
            v[++h]=x;
            poz[++cnt]=x;
            M[x]=h;
            SiftUp(h);
        }
        else if(cer==2)
        {
            f>>x;
            M[v[h]]=M[poz[x]],swap(v[M[poz[x]]],v[h--]),SiftDown(M[poz[x]]);
        }
        else
            g<<v[1]<<'\n';
    }

    return 0;
}