#include<iostream>
#include<fstream>
#include<assert.h>
using namespace std;

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

int N,L,NR;
int A[200010],Heap[200010], Poz[200010];

void Push(int x)
{
	int aux;
	while(x/2 && A[Heap[x]]<A[Heap[x/2]])
	{
		aux=Heap[x];
		Heap[x]=Heap[x/2];
		Heap[x/2]=aux;
		
		Poz[Heap[x]]=x;
		Poz[Heap[x/2]]=x/2;
		x=x/2;
	}
}

void Pop(int x)
{
	int aux, y=0;
	while(x!=y)
	{
		y=x;
		if(y*2<=L && A[Heap[x]]>A[Heap[y*2]])
			x=y*2;
		if(y*2+1<=L && A[Heap[x]]>A[Heap[y*2+1]])
			x=y*2+1;
		
		aux=Heap[x];
		Heap[x]=Heap[y];
		Heap[y]=aux;
		
		Poz[Heap[x]]=x;
		Poz[Heap[y]]=y;
	}
}

int main()
{
	int i, x, cod;
	fin>>N;
	assert(1<=N && N<=200000);
	
	for(i=1;i<=N;i++)
	{
		fin>>cod;
		assert(1<=cod && cod<=3);
		if(cod<3)
		{
			fin>>x;
			assert(1<=x && x<=1000000000);
		}
		if(cod==1)
		{
			L++;
			NR++;
			A[NR]=x;
			Heap[L]=NR;
			Poz[NR]=L;
			Push(L);
		}
		if(cod==2)
		{
			A[x]=-1;
			assert(Poz[x]!=0);
			assert(1<=x && x<=NR);
			Push(Poz[x]);
			Poz[Heap[1]]=0;
			Heap[1]=Heap[L--];
			Poz[Heap[1]]=1;
			if(L>1)
				Pop(1);
		}
		if(cod==3)
			fout<<A[Heap[1]]<<"\n";
	}
	
	return 0;
}