#include <stdio.h>
#include <algorithm>
using namespace std;
int h[200001], poz[200001], ord[200001], l;
/*
void push(int x) {
    n++;
    heap[n]=x;
    int i = n;
    while(i > 1 && heap[i] < heap[i/2]) {
        swap(heap[i],heap[i/2]);
        swap(poz[n],poz[i/2]);
        i /= 2;
    }
}
void pop(int i) {
    int x = heap[i];
    while(i*2 <= n) {
        if(heap[i*2+1] == 0) {
            heap[i] = heap[i*2];
            i *= 2;
        }
        else {
            heap[i] = heap[i*2] <= heap[i*2+1] ? heap[i*2] : heap[i*2+1];
            i = heap[i*2] <= heap[i*2+1] ? i*2 : i*2+1;
        }
    }
}
*/
void up(int i) {
    while(i > 1 && h[i] < h[i/2]) {
        swap(h[i],h[i/2]);
        swap(ord[i],ord[i/2]);
        poz[ord[i/2]] = i/2;
        poz[ord[i]] = i;
        i/=2;
    }
}
void down(int i) {
    int ind;
    while(i < l && h[i] > min(h[i*2],h[i*2+1])) {
        //ind = h[i*2] <= h[i*2+1] ? ind=i*2 : ind=i*2+1;
        if(h[i*2] <= h[i*2+1])
            ind = i*2;
        else ind = i*2+1;
        if(i >= l/2 && l%2 == 1)
            ind = i*2;
        swap(h[i],h[ind]);
        swap(ord[i],ord[ind]);
        poz[ord[ind]] = ind;
        poz[ord[i]] = i;
        i=ind;
    }
}
int main()
{
    freopen("heapuri.in","r",stdin);
    freopen("heapuri.out","w",stdout);
    int k, cod, i, p, x;
    scanf("%d",&k);
    for(i=1, p=0;i<=k;i++) {
        scanf("%d",&cod);
        if(cod == 1) {
            scanf("%d",&x);
            p++; l++;
            h[l] = x;
            poz[p] = l;
            ord[l] = p;
            up(l);
        }
        if(cod == 2) {
            scanf("%d",&x);
            h[poz[x]] = h[l];
            l--;
            up(poz[x]);
            down(poz[x]);
        }
        if(cod == 3) {
            printf("%d\n",h[1]);
        }
    }
    return 0;
}