#include <fstream>
using namespace std;

ifstream FIn("heapuri.in");
ofstream FOut("heapuri.out");

const int NMax=1<<18;
int V[NMax],POZ[NMax],H[NMax],N,H_Size,Nr;

inline int H_Father(int x){
	return x/2;
}

inline int H_LeftSon(int x){
	return x*2;
}

inline int H_RightSon(int x){
	return x*2+1;
}

void H_ReBuildFather(int x){
	int f=H_Father(x);
	if(f==0){
		return;
	}
	if(V[H[f]]>V[H[x]]){
		POZ[H[f]]=x;
		POZ[H[x]]=f;
		int aux=H[f];
		H[f]=H[x];
		H[x]=aux;
		H_ReBuildFather(f);
	}
}

void H_ReBuild(int x){
	int l=H_LeftSon(x),r=H_RightSon(x),son=x;
	son=(l<=H_Size&&V[H[l]]<V[H[x]])?l:son,son=(r<=H_Size&&V[H[r]]<V[H[x]])?r:son;
	if(son!=x){
		POZ[H[x]]=son;
		POZ[H[son]]=x;
		int aux=H[x];
		H[x]=H[son];
		H[son]=aux;
		H_ReBuild(son);
	}
}

void H_Insert(){
	FIn>>V[++N];
	H[++H_Size]=N;
	POZ[N]=H_Size;
	H_ReBuildFather(H_Size);
}

void H_Cut(){
	int q;
	FIn>>q;
	H[POZ[q]]=H[H_Size];
	POZ[H[H_Size]]=POZ[q];
	--H_Size;
	H_ReBuildFather(POZ[q]);
	H_ReBuild(POZ[q]);
}

void EXE(),IN(),DO();
int main(){EXE();return 0;}

void EXE(){
	IN();
	for(;Nr--;DO());
}

void IN(){
	FIn>>Nr;
}

void DO(){
	int o;
	FIn>>o;
	if(o==1){
		H_Insert();
		return;
	}
	if(o==2){
		H_Cut();
		return;
	}
	FOut<<V[H[1]]<<"\n";
}