#include <bits/stdc++.h>
 
#define pb push_back 
#define x first 
#define y second 
#define MOD 1000000007
 
using namespace std;
typedef long long ll;
typedef pair< int , int > PII;
const int dirx[] = {-2,-1,1,2, 1, -1};
const int diry[] = {0,1,1,0, -1, -1};
inline void debugMode() {
    #ifndef ONLINE_JUDGE
    freopen("heapuri.in", "r", stdin);
    freopen("heapuri.out", "w", stdout);
    #endif
}
 
int n, m, Heap[500100], INS[200100], cnt, POS[200100];
 
void down(int n, int p){
    int son;
    do{
        son = (p << 1) * (p << 1 <= n) + ((p << 1 | 1) <= n && INS[Heap[p << 1 | 1]] < INS[Heap[p << 1]]);
        if (son){
            swap(POS[Heap[son]], POS[Heap[p]]);
            swap(Heap[son], Heap[p]);
            p = son;
 
        }
    } while (son);
}
 
void up(int p){
    while (p > 1 && INS[Heap[p]] < INS[Heap[p >> 1]]){
        swap(POS[Heap[p]], POS[Heap[p >> 1]]);
        swap(Heap[p], Heap[p >> 1]);
        p >>= 1;
    }
}
 
void insert(int val){
    Heap[n] = val;
    up(n);
}
 
void cut(int &n, int p){
    POS[Heap[p]] = p;
    Heap[p] = Heap[n];
    n--;
    if (n > 1 && INS[Heap[p]] < INS[Heap[p >> 1]]) up(p);
    else down(n, p);
}
 
int main(){
    debugMode();
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> m;
    for (int i = 1, a, b; i <= m; i++){
        cin >> a;
        if (a == 3) cout << INS[Heap[1]] << "\n";
        else{
            cin >> b;
            if (a == 1){
                ++cnt, ++n;
                INS[cnt] = b;
                POS[cnt] = n;
                insert(cnt);
            }
            else cut(n, POS[b]);
        }
    }
     
 
    return 0;
}