#include <bits/stdc++.h>

using namespace std;

ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

pair<int, int> heap[200001];
int poz[200001];
int siz = 1;

void addH(int x){
    heap[siz].first = x;
    heap[siz].second = siz;
    poz[siz] = siz;
    siz++;
    int it = siz - 1;
    while(it > 1){
        if(heap[it / 2].first > heap[it].first){
            swap(heap[it], heap[it / 2]);
            swap(poz[ heap[it].second  ], poz[ heap[it / 2].second ]);
            it /= 2;
        }else break;
    }
}

void up(int x){
    int it = x;
    while(it > 1){
        if(heap[it / 2].first > heap[it].first){
            swap(heap[it], heap[it / 2]);
            swap(poz[ heap[it].second  ], poz[ heap[it / 2].second ]);
            it /= 2;
        }else break;
    }
}

int main(){
    cin.tie(0);ios::sync_with_stdio(0);

    int n; fin >> n;
    /*
    for(int ii = 0; ii < n; ii++){
        int op; cin >> op;
        if(op == 3) fout << heap[1].first << endl;
        else if(op == 1){
            int x; fin >> x;
            addH(x);    
        }else{
            int x; cin >> x;
            //cout << "Eliminam pozitia " << poz[x] << " din heap, cu elementul " << heap[ poz[x] ].first << endl;
            x = poz[x];
            swap(poz[ heap[x].second  ], poz[ heap[ siz - 1  ].second ]);
            swap(heap[x], heap[siz - 1]);
            siz--;
            heap[siz].first = 0;
            poz[ heap[x].second  ] = 0;

            int it = 1;
            while(it * 2 < siz){
                //cout << "it = " << it << " el = " << heap[it].first << endl;
                if( min(heap[it * 2].first, heap[it * 2 + 1].first) < heap[it].first  ){ // dam swap
                    if( heap[it * 2].first > heap[it * 2 + 1].first && heap[2 * it + 1].first != 0 ){
                        swap( poz[ heap[it].second ], poz[ heap[ it * 2 + 1].second ] );
                        swap( heap[it], heap[it * 2 + 1] );
                        it = it * 2 + 1;
                    }else{
                        swap( heap[it], heap[it * 2] );
                        swap( poz[ heap[it].second  ], poz[ heap[it * 2].second ] );
                        it = it * 2;
                    }
                }else break;
            }
            up(x);
        }

        cout << "heap : ";
        for(int i = 1; i < siz; i++) cout << heap[i].first<< " ";
        cout << endl;
        cout << "poz : ";
        for(int i = 1; i < siz; i++) cout << poz[i] << " ";
        cout << endl;
    }*/

    priority_queue< int, vector<int>, greater<int> > p1;
    priority_queue< int, vector<int>, greater<int> > p2;
    vector <int> elm;

    for(int ii = 0; ii < n; ii++){
        int op; fin >> op;
        if(op == 1){
            int x; fin >> x;
            p1.push(x);
            elm.push_back(x);
        }else if(op == 2){
            int x; fin >> x;
            x = elm[x - 1];
            p2.push(x);
        }else{
            while(!p1.empty() && !p2.empty() && p1.top() == p2.top()){
                p1.pop();
                p2.pop();
            }
            fout << p1.top() << endl;
        }
    }

    return 0;
}