#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <deque>
#include <algorithm>
#define ll long long

using namespace std;
ifstream f("heapuri.in");
ofstream g("heapuri.out");
int n,i,j,k,v[200005],A[200005],poz[200005],m,Size,op,val;

void upheap(int nod, int Start, int End)
{
    int father=nod/2;
    if(nod>=2*Start)
    {
        if(v[A[father]]>v[A[nod]])
        {
            swap(poz[A[father]],poz[A[nod]]);
            swap(A[father],A[nod]);
            upheap(father,Start,End);
        }
    }
}

void downheap(int nod, int Start, int End)
{
    int left=nod*2;
    int right=left+1;
    int fiu=0;
    int mini=v[A[nod]];
    if(left<=End && v[A[left]]<mini) fiu=left, mini=v[A[left]];
    if(right<=End && v[A[right]]<mini) fiu=right, mini=v[A[right]];
    if(fiu)
    {
        swap(poz[A[nod]],poz[A[fiu]]);
        swap(A[nod],A[fiu]);
        downheap(fiu, Start, End);
    }
}

int main()
{
    f>>m;
    Size=0;
    while(m)
    {
        f>>op;
        if(op==1)
        {
            f>>val;
            ++Size; ++n;
            A[Size]=n;
            v[n]=val;
            poz[n]=Size;
            upheap(Size,1,Size);
        }
        else if(op==2)
        {
            f>>val;
            poz[A[Size]]=poz[val];
            A[poz[val]]=A[Size];
            val=A[Size];
            Size--;
            upheap(poz[val],1,Size);
            downheap(poz[val],1,Size);
        }
        else
        {
            g<<v[A[1]]<<'\n';
        }
        m--;
    }
    return 0;
}