#include<bits/stdc++.h>   //heap
#define ll long long
#define sz size
#define pb push_back
#define er erase
#define in insert
#define fr first
#define sc second
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
using namespace std;

const int N=200005;
char t;
int heap[N],x,n,j,k,q,tim,pros[N],vrem[N];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    freopen("heapuri.in","r",stdin);
  	freopen("heapuri.out","w",stdout);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> t;
        if(t=='1'){
            cin >> k;
            q++;
            heap[q]=k;
            tim++;
            //
            vrem[tim]=q;
            pros[q]=tim;
            //
            int pos=q;
            while(heap[pos/2]>heap[pos] && pos/2>=1){
                swap(vrem[tim],vrem[pros[pos/2]]);
                swap(pros[pos],pros[pos/2]);
                swap(heap[pos/2],heap[pos]);
                pos/=2;
            }
        }
        if(t=='2'){
            cin >> k;
            vrem[pros[q]]=vrem[k];
            pros[vrem[k]]=pros[q];
            swap(heap[q],heap[vrem[k]]);
            int pos=vrem[k];
            q--;
            while(heap[pos/2]>heap[pos] && pos/2>=1){
                swap(vrem[tim],vrem[pros[pos/2]]);
                swap(pros[pos],pros[pos/2]);
                swap(heap[pos/2],heap[pos]);
                pos/=2;
            }
            while((heap[pos]>heap[2*pos] && 2*pos<=q) || (heap[pos]>heap[2*pos+1] && 2*pos+1<=q)){
                if(heap[pos]>heap[2*pos] && 2*pos<=q){
                    swap(vrem[tim],vrem[pros[2*pos]]);
                    swap(pros[pos],pros[2*pos]);
                    swap(heap[2*pos],heap[pos]);
                    pos*=2;
                    continue;
                }
                if(heap[pos]>heap[2*pos+1] && 2*pos+1<=q){
                    swap(vrem[tim],vrem[pros[2*pos+1]]);
                    swap(pros[pos],pros[2*pos+1]);
                    swap(heap[2*pos+1],heap[pos]);
                    pos*=2;
                    pos++;
                    continue;
                }
            }
        }
        if(t=='3'){
        	cout<<heap[1]<<endl;
		}
        //for(int i=1;i<=q;i++){
        //	cout<<heap[i]<<' ';
		//}
		//cout<<endl;
		
        
        
    }
     
     
     
/*    for(int i=1;i<=g;i++){
        cout<<heap[i]<<' ';
    }
    cout<<endl;
    for(int i=1;i<=g;i++){
        cout<<vrem[i]<<' ';    
    } */
}