#include <bits/stdc++.h>
#define MAX 131072

using namespace std;
const int NMAX = 200010;

FILE *IN;

struct event{
    int x, p;
}heap[NMAX];

int N, M;
int poz[NMAX];

int pos, sign;
char f[MAX];

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[pos] < '0' || f[pos] > '9'){
        if(f[pos] == '-') sign = 1;
        pos++;
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    while(f[pos] >= '0' && f[pos] <= '9'){
        nr = 10 * nr + f[pos++] - '0';
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    if(sign) nr =- nr;
}

void upHeap(int node){
    if(heap[node].x < heap[node / 2].x && node > 1){
        swap(heap[node], heap[node / 2]);
        swap(poz[heap[node].p], poz[heap[node / 2].p]);
        upHeap(node / 2);
    }
}

void downHeap(int node){
    if(2 * node > M)
        return;
    if(heap[node].x > heap[2 * node].x && (heap[2 * node].x < heap[2 * node + 1].x || 2 * node == M)){
        swap(heap[node], heap[2 * node]);
        swap(poz[heap[node].p], poz[heap[2 * node].p]);
        downHeap(2 * node);
    } else if(heap[node].x > heap[2 * node + 1].x && heap[2 * node + 1].x < heap[2 * node].x){
        swap(heap[node], heap[2 * node + 1]);
        swap(poz[heap[node].p], poz[heap[2 * node + 1].p]);
        downHeap(2 * node + 1);
    }
}

int main(){

    IN = fopen("heapuri.in", "r");
    freopen("heapuri.out", "w", stdout);

    Read(N);

    int tip, x;
    int cnt = 1;
    for(int i = 1; i <= N; i++){
        Read(tip);
        if(tip == 1){
            Read(x);
            heap[++M].x = x;
            poz[M] = heap[M].p = cnt;
            cnt++;
            upHeap(M);
        } else if(tip == 2){
            Read(x);
            swap(heap[poz[x]], heap[M]);
            int p = poz[heap[M].p];
            swap(poz[heap[poz[x]].p], poz[heap[M].p]);
            M--;
            downHeap(p);
        } else printf("%d\n", heap[1].x);
    }

    return 0;
}