#include <bits/stdc++.h>

using namespace std;

int s[200055];

int v[200055];

int f[200055];

int in=0;

int n,c,x,ix=0;

void up(int k)
{
    int i=k;
    while(i>1 && v[s[i]]<v[s[i/2]])
    {
        f[s[i]]=i/2;
        f[s[i/2]]=i;
        swap(s[i],s[i/2]);
        i=i/2;
    }
}

void dn(int k)
{
    int i=k;
    bool ok=true;
    while(ok)
    {
        ok=false;
        int ii=i*2;
        if(i*2<=in && i*2+1<=in && v[s[i*2+1]]<v[s[i*2]])
        {
            ii=i*2+1;
        }
        if(ii<=in && v[s[i]]>v[s[ii]])
        {
                    f[s[i]]=ii;
        f[s[ii]]=i;
            swap(s[i],s[ii]);
            i=ii;
            ok=true;

        }
    }
}

int main()
{
    ifstream cin("heapuri.in");
    ofstream cout("heapuri.out");
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>c;
        if(c==1)
        {
            cin>>x;
                    ++ix;
        v[ix]=x;
            ++in;
            s[in]=ix;
            f[ix]=in;
            up(in);
            if(x==2)
            {
                //cout<<v[s[1]]<<" "<<in<<"     ";
            }
        }
        else if(c==2)
        {
            cin>>x;
            f[s[in]]=f[x];
            swap(s[f[x]],s[in]);
            --in;
            up(f[x]);
            dn(f[x]);
        }
        else
        {
            cout<<v[s[1]]<<"\n";
        }
    }
    return 0;
}