//pattern matching
//KMP-in O(n+m)
/*#include<iostream>
#include<cstring>
#include<fstream>
#define N 2000005
using namespace std;

char P[N],T[N];
int m,n,poz[N],st[1024];

void citire()
{
    int i;
    ifstream fin("strmatch.in");
    fin.getline(P,sizeof(P));
    fin.getline(T,sizeof(T));
    for (; (P[m] >= 'A' && P[m] <= 'Z') || (P[m] >= 'a' && P[m] <= 'z')

			|| (P[m] >= '0' && P[m] <= '9'); ++m);

	for (; (T[n] >= 'A' && T[n] <= 'Z') || (T[n] >= 'a' && T[n] <= 'z')

			|| (T[n] >= '0' && T[n] <= '9'); ++n);

	for (i = m; i; --i) P[i] = P[i-1];

	for (i = n; i; --i) T[i] = T[i-1];
    P[0]=' ';
    T[0]=' ';

    fin.close();

}


void constr()
{
    poz[1]=0;
    int k=0;
    for(int q=2;q<=m;q++)
    {
        while(k>0 && P[k+1]!=P[q])
            k=poz[k];
        if(P[k+1]==P[q]) k++;
        poz[q]=k;
    }

}

void KMP()
{
    int q=0,i,ans=0;
    for(i=1;i<=n;i++)
    {
        while(q && P[q+1]!=T[i])
            q=poz[q];
        if(P[q+1]==T[i]) q++;
        if(q==m)
           {
               //cout<<i-m<<' ';
               q=poz[q];
               ans++;
               if(ans<=1000)
               st[ans]=i-m;


           }

    }
    ofstream fout("strmatch.out");
    fout<<ans<<endl;
    for(i=1;i<=min(1000,ans);i++)
        fout<<st[i]<<' ';
    fout.close();


}



int main()
{
    citire();
    constr();
    //for(int i=1;i<=m;i++) cout<<poz[i]<<' ';
    KMP();
}*/

//heapsort
/*#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;

int H[100],n;

void read()
{
    ifstream fin("heapuri.in");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>H[i];
    fin.close();
}

void CombHeap(int i,int m)     //O(log n)
{
    int v=H[i],tata=i,fiu=i*2;
    while(fiu<=m)
    {
        if(fiu<m)
            if(H[fiu]<H[fiu+1]) fiu++;
        if(v<H[fiu])
        {
            H[tata]=H[fiu];
            tata=fiu;
            fiu=fiu*2;
        }
        else fiu=m+1;
    }
    H[tata]=v;


}



void CreareHeap()
{
    for(int i=n/2;i;i--)
        CombHeap(i,n);
}



void heap_sort()
{
    int aux;
    CreareHeap();
    for(int i=n;i>1;i--)
    {
        aux=H[1];
        H[1]=H[i];
        H[i]=aux;
        CombHeap(1,i-1);
    }
}

//coada cu dubla prioritate
//min-max heap


void Insert(int x)
{
    //O(log n)
    int niv,fiu,tata;
    H[++n]=x;
    if(n<=1) return;
    fiu=n;
    niv=log2(n);
    if(niv%2==1) //val de inserat se afla pe nivel maxim
    {
        tata=n/2; //nivel minim
        if(x<H[tata])
        {
            while(tata && x<H[tata])
            {
                H[fiu]=H[tata];
                fiu=tata;
                tata=tata/4;

            }
            H[fiu]=x;
        }
        else
        {
            tata=fiu/4;
            while(tata && x>H[tata])
            {
                H[fiu]=H[tata];
                fiu=tata;
                tata=tata/4;

            }
            H[fiu]=x;

        }
    }

    else
        //inseram pe un nivel minim
    {
        tata=n/2;
    if(x>H[tata])
    {
        while(tata && x>H[tata])
        {
            H[fiu]=H[tata];
            fiu=tata;
            tata=tata/4;
        }
        H[fiu]=x;
    }
    else
    {
        tata=fiu/4;
        while(tata && x<H[tata])
        {
            H[fiu]=H[tata];
            fiu=tata;
            tata/=4;
        }
        H[fiu]=x;

    }

    }
}


void print()
{
    for(int i=1;i<=n;i++)
        cout<<H[i]<<' ';
    cout<<endl;
}

int main()
{
    read();
    //heap_sort();
    //Insert(2);
    print();
}*/

//2014
/*#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

//b
int dei(int n)
{
    if(n==1 || n==4)
        return 1;
    if(n==2 ||n==3)
        return 2;
    int k,it=1,c,exp=4;
    //k=(log2(n))/2;
    //c=n/pow(4,k);
    //if(c==2 || c==3) return 3-dei(n-c*pow(4,k));
    //else return dei(n-c*pow(4,k));
    while(exp<=n)
    {
        exp*=4;
        it++;
    }
    --it;
    exp/=4;
    //exp=4^k
    c=n/exp;
    if(n==c*exp)
    {
        if(c==2 || c==3) return 3-dei(exp);
        if(c==1) return 1;
    }
    if(c==1 || c==2) return 3-dei(n-c*exp);
    if(c==3) return dei(n-c*exp);

}



int main()
{
    int n,k,dims=4,i,verificare=0;
    cin>>n;
    k=(int)(log2(n))/2;
    char s[(int)pow(4,k+1)];
    s[1]=s[4]=1;
    s[2]=s[3]=2;
    //a
    while(dims<=n)
    {
        for(i=1;i<=dims;i++)
            s[i+dims]=3-s[i];
        for(i=dims+1;i<=dims*2;i++)
            s[i+dims]=3-s[i-dims];
        for(i=dims*2+1;i<=dims*3;i++)
            s[i+dims]=s[i-2*dims];
        dims*=4;
    }

    for(i=1;i<=n;i++)
        if(s[i]==dei(i)) verificare++;
    if(verificare==n) cout<<"corect!";
    //e bine :)))

}*/

/*#include<iostream>
#include<fstream>
using namespace std;

struct nod{int inf;nod *adr;};

nod *steeve;

void push(nod *&p,int x)
{
    nod *nou;
    nou=new nod;
    nou->inf=x;
    nou->adr=p;
    p=nou;

}


void pop(nod *&p)
{
    nod *nou;
    nou=new nod;
    nou=p;
    p=p->adr;
    delete nou;

}

int isempty(nod *p)
{
    return (p==NULL);
}

int top(nod *p)
{
    return p->inf;

}

int main()
{
    char s[100],x;
    ifstream fin("text.in");

    steeve=NULL;
    while(fin>>x)
    {if(isempty(steeve)) push(steeve,x);
    else
        if(x=='(') push(steeve,x);
        if(x==')')
        {if(top(steeve)=='(') pop(steeve);
        else push(steeve,top(steeve));
        }

    }
    if(isempty(steeve)) cout<<"corect";
    else cout<<"incorect";

}*/

//heapuri-infoarena
/*#include<bits/stdc++.h>
using namespace std;

int H[100],n,Pos[100],nr;

void read()
{
    ifstream fin("heapuri.in");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>H[i];
    fin.close();
}


void sift(int m,int poz)
{
    int fiu;
    do
    {
        fiu=0;
        //verific daca fiul exista
        if(poz*2<=m)
        {
            fiu=poz*2;
            if(H[fiu]<H[fiu+1] && fiu+1<=m)
                fiu++;
            if(H[poz]>=H[fiu]) fiu=0;

        }
        if(fiu)
        {
            swap(H[fiu],H[poz]);
            poz=fiu;
        }

    }
    while(fiu);

}

//alternativ
void CombHeap(int i,int m)     //O(log n)
{
    int v=H[i],tata=i,fiu=i*2;
    while(fiu<=m)
    {
        if(fiu<m)
            if(H[fiu]<H[fiu+1]) fiu++;
        if(v<H[fiu])
        {
            H[tata]=H[fiu];
            tata=fiu;
            fiu=fiu*2;
        }
        else fiu=m+1;
    }
    H[tata]=v;


}


void percolate(int poz)
{
    int comp=H[poz];
    while(poz>1 && H[poz]>H[poz/2])
    {
        swap(H[poz],H[poz/2]);
        poz=poz/2;
    }
}


void create_heap()
{
    for(int i=n/2;i;i--)
        sift(n,i);
}



void delete_heap(int poz)
{
    //deoarece heap-ul este un arbore binar complet, pentru a se conserva proprietatea sa, trebuie sa adaugam ultimul nod, cel de "umplutura"
    //in locul celui sters, iar apoi sa l asezam pe pozitia corecta
    H[poz]=H[n--];
    if(poz/2>=1 && H[poz]>H[poz/2])
        percolate(poz);
    if(H[poz]<H[poz*2] && poz*2<=n)
        sift(n,poz);
    //O(log n)

}

void print_heap()
{
  for(int i=1;i<=n;i++)
        cout<<H[i]<<' ';
    cout<<'\n';
}

void insert_heap(int x)
{
    H[++n]=x;
    if(x/2>=1 && x>H[x/2])
        percolate(n);
}

void heapsort()
{
    int i,aux;
    for(i=n;i>1;i--)
    {
        swap(H[1],H[i]);
        sift(i-1,1);
    }
}

//cautare-de aia exista arbori binari de cautare

int main()
{
    read();
    create_heap();
    //delete_heap(2);
    //insert_heap(13);
    heapsort();
    print_heap();
}*/


#include<bits/stdc++.h>
#define nmax 200000
using namespace std;

int H[nmax],n,v[nmax],Pos[nmax],nr;


void read()
{
    ifstream fin("heapuri.in");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>H[i];
    fin.close();
}


void insert_heap(int x)
{
    while(x/2 && v[H[x]]<v[H[x/2]])
    {
        swap(H[x],H[x/2]);
        //Poz[i] reprezinta pozitia in heap a elementului v[i]
        Pos[H[x]]=x;
        Pos[H[x/2]]=x/2;
        x=x/2;

    }

}

void delete_em(int x)
{
    int y=-2;
    //fiind mai mic decat restul valorilor din heap
    while(x!=y)
    {
        y=x;
        if(2*x<=n && v[H[x]]>v[H[2*x]])
            x=2*y;
        if(2*y+1<=n && v[H[x]]>v[H[2*y+1]])
            x=2*y+1;
        if(x!=y)
        {
            //H[i]=poz in v a elementului i din heap
            Pos[H[x]]=y;
            Pos[H[y]]=x;
            swap(H[x],H[y]);

        }

    }

}


void print_heap()
{
    for(int i=1;i<=n;i++)
        cout<<v[H[i]]<<' ';
        cout<<'\n';

}


void solve_heapuri(int &N)
{
    ifstream fin("heapuri.in");
    ofstream fout("heapuri.out");
    int i,x,c,poz;
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>c;
        if(c==1)
        {
            fin>>x;
            v[++nr]=x;
            H[++n]=nr;
            //sigur nu se incaleca, caci l am sters pe H[Pos[x]] in cazul 2
            Pos[nr]=n;
            //Pos[i]=pozitia in heap a lui v[i]
            insert_heap(n);

        }
        else if(c==2)
        {
            fin>>x;
            v[x]=-1;
            H[Pos[x]]=H[n--];
            Pos[H[Pos[x]]]=Pos[H[n]];
            delete_em(Pos[x]);
            Pos[x]=0;
            //print_heap();
        }
        else
            fout<<v[H[1]]<<'\n';

    }

}

int main()
{
    int N;
    solve_heapuri(N);

}