#include <bits/stdc++.h>

using namespace std;

ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

const int N=200010;
typedef int Heap;

Heap h[N];
int A[N],pos[N],op,x,L,cnt,q;

void push()
{
    int aux=L;
    while(aux && A[h[aux]]<A[h[aux/2]])
    {
        swap(h[aux],h[aux/2]);
        pos[h[aux]]=aux;
        pos[h[aux/2]]=aux/2;
        aux/=2;
    }
}

void pop()
{
    int aux=L;
    int fiu=2*aux;
    if(fiu>L)return;
    if(A[h[fiu]]>A[h[fiu+1]])fiu++;
    while(2*aux<L)
    {
        if(A[h[aux]]>A[h[fiu]])
        {
            swap(h[aux],h[fiu]);
            pos[h[aux]]=aux;
            pos[h[fiu]]=fiu;
        }else break;
        aux*=2;
        fiu*=2;
    }
}

int main()
{
    fin>>q;
    for(;q;q--)
    {
        fin>>op;
        if(op<3)
        {
            fin>>x;
            if(op==1)
            {
                L++;
                cnt++;
                A[cnt]=x;
                h[L]=cnt;
                pos[cnt]=L;
                push();
            }
            if(op==2)
            {
                int poz=pos[x];
                swap(h[poz],h[L]);
                pos[h[poz]]=poz;
                pos[h[L]]=L;
                L--;
                push();
                pop();
            }
        }else fout<<A[h[1]]<<'\n';
    }
    return 0;
}