#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

const int cons=200003;
int n[cons],ord[cons];

ifstream fin ("heapuri.in");
ofstream fout ("heapuri.out");
priority_queue<int> q;

void sorta(int poz)
{
    while(n[poz]<n[poz>>1] && poz>>1!=0)
    {
        swap(n[poz],n[poz>>1]);
        poz=poz>>1;
    }
}

void ins(int arg)
{
    if(!q.empty())
    {
        int poz=-q.top();
        n[poz]=arg;
        sorta(poz);
        if(poz>n[0])
            n[0]=poz;
        q.pop();
    }
    else
    {
        n[n[0]]=arg;
        sorta(n[0]);
        n[0]++;
    }

}

void ster(int poz)
{
    while(true)
    {
        int poz1=poz<<1;
        if(n[poz1]==-1)
        {
            n[poz]=-1;
            q.push(-poz);
            break;
        }
        if(n[poz1+1]==-1)
        {
            swap(n[poz1],n[poz]);
            n[poz1]=-1;
            q.push(-poz1);
            break;
        }
        if(n[poz1]<n[poz1+1])
        {
            swap(n[poz1],n[poz]);
            poz=poz1;
        }
        else
        {
            swap(n[poz1+1],n[poz]);
            poz=poz1+1;
        }
    }
}

void gas(int arg)
{
    for(int k=1;true;k++)
    {
        if(n[k]==ord[arg])
        {
            ster(k);
            return;
        }
    }
}

int main()
{
    n[0]=1;
    int n;
    int op,arg;
    fin>>n;
    for(int k=1;k<=cons;k++)
        ::n[k]=-1;
    for(int k=1;k<=n;k++)
    {
        fin>>op;
        if(op==3)
            fout<<(::n[1])<<'\n';
        else
        {
            fin>>arg;
            if(op==1)
            {
                ins(arg);
                ord[++ord[0]]=arg;
            }
            else
                gas(arg);
        }
    }
    return 0;
}