#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
#define MaxN 200000

int poz[MaxN];
priority_queue<int, vector<int>, greater<int> > pq1;
priority_queue<int, vector<int>, greater<int> > pq2;

int main()
{
    ifstream in("heapuri.in");
    ofstream out("heapuri.out");
    int n, cer, i, x, cnt=0;
    in>>n;
    for(i=0; i<n; i++)
    {
        in>>cer;
        if(cer==3)
        {

            while( pq2.size()>0 && pq1.top()==pq2.top())
            {
                pq1.pop();
                pq2.pop();
            }
            out<<pq1.top()<<'\n';
        }
        else if(cer==1)
        {
            in>>x;
            pq1.push(x);
            cnt++;
            poz[cnt]=x;
        }
        else
        {
            in>>x;
            pq2.push(poz[x]);
        }

    }


    return 0;
}