#include <bits/stdc++.h>
#define NMAX 1000005

using namespace std;

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

int n , x;
int a[NMAX] , poz[NMAX] , poz_heap[NMAX];
short operatie;

stack < int > poz_x;

int father(int n)
{
    return n / 2;
}

int right_son(int n)
{
    return 2 * n + 1;
}

int left_son(int n)
{
    return 2 * n;
}

void Build_Heap(int &k)
{
    int val = a[k];

    while(k > 1 && val < a[father(k)])
    {
        poz_heap[k] = poz_heap[father(k)];
        poz[poz_heap[k]] = k;
        a[k] = a[father(k)];
        k = father(k);
    }

    a[k] = val;
}

void Delete(int &k , int n , int &poz_son)
{
    int son = 0;

    do
    {
        if(left_son(k) <= n)
        {
            if(right_son(k) <= n && a[left_son(k)] > a[right_son(k)])
                son = right_son(k);
            else if(a[left_son(k)] != 1000000001 && left_son(k) <= n)
                son = left_son(k);
            else son = 0;
        }
        else son = 0;

        if(son)
        {
            poz_heap[k] = poz_heap[son];
            poz[poz_heap[k]] = k;

            a[k] = a[son];
            poz_son = son;
            k = son;
        }
    }while(son);
}

int main()
{
    int poz_son = 0;

    f >> n;

    for(int i = 1 ; i <= n ; i++)
    {
        f >> operatie;

        if(operatie == 1)
        {
            if(!poz_x.empty())
            {
                f >> x;

                a[poz_x.top()] = x;
                int k = poz_x.top();
                Build_Heap(k);
                poz[poz_x.top()] = k;
                poz_heap[k] = poz_x.top();
                poz_x.pop();
                continue;
            }

            f >> a[++a[0]];

            int k = a[0];
            Build_Heap(k);
            poz[a[0]] = k;
            poz_heap[k] = a[0];
        }
        else if(operatie == 2)
        {
            f >> x;

            poz_son = 0;
            Delete(poz[x] , a[0] , poz_son);
            poz_x.push(poz_son);
            a[poz_son] = 1000000001;
        }
        else g << a[1] << '\n';
    }

    return 0;
}