#include <bits/stdc++.h>
using namespace std;
int n, i, v[200001], k, val, x, nr, H[200001], pozh[200001];

void DownHeap (int poz, int n)
{
    while (poz*2<=n) {
        int st=poz*2;
        if (st+1<=n && v[H[st]]>v[H[st+1]])
            st=st+1;
        if (v[H[poz]]>v[H[st]]) {
            pozh[H[poz]]=st;
            pozh[H[st]]=poz;
            swap(H[poz], H[st]);
            poz=st;
        }else
            break;
    }
}
void UpHeap (int poz)
{
    int x=H[poz];
    int p=poz;
    while (poz/2>0 && v[H[poz/2]]>v[x]) {

        H[poz]=H[poz/2];
         pozh[H[poz]]=poz;
        poz/=2;
    }
    H[poz]=x;
    pozh[x]=poz;
}
int main () {
    ifstream fin ("heapuri.in");
    ofstream fout ("heapuri.out");
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>val;
        if (val==1) {
            fin>>x;
            v[++nr]=x;
            H[++k]=nr;
            pozh[nr]=k;
            UpHeap(k);
        }else if (val==2) {
            fin>>x;
            int poz=pozh[x];
            pozh[H[k]]=poz;
            pozh[H[poz]]=k;
            swap(H[poz], H[k]);
            k--;
            DownHeap(poz, k);
            UpHeap(poz);
        } else {
            fout<<v[H[1]]<<"\n";
        }
    }

    return 0;
}