#include <bits/stdc++.h>

using namespace std;

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

int a[200001],poz[200001],heap[200001],viz[200001],k=0;
int len=0;

void add(int x)
{
	int current=x;
	while(a[heap[current/2]]>a[heap[current]] && current>1)
	{
		swap(heap[current],heap[current/2]);
		current/=2;
	}
}

void del(int x)
{
	if(2*x<=len)
	{
		int l,r;
		l=a[heap[2*x]];
		if(2*x+1<=len)
			r=a[heap[2*x+1]];
		else
			r=l+1;
		if(min(l,r)<a[heap[x]])
		{
			if(l<r)
			{
				swap(heap[x],heap[2*x]);
				del(2*x);
			}
			else
			{
				swap(heap[x],heap[2*x+1]);
				del(2*x+1);
			}
		}
	}

}

void first(int x)
{
	k++;
	len++;
//	int current=len;
	a[k]=x;
	heap[len]=k;
	poz[k]=len;
	add(len);
}

void third()
{	
	while(viz[heap[1]]==1)
	{
		swap(heap[1],heap[len]);
		len--;
		del(1);
	}
	out<<a[heap[1]]<<"\n";
}


int main()
{
	int n;
	in>>n;
	for(int i=1;i<=n;i++)
	{
		int cod,x;
		in>>cod;
		if(cod==1||cod==2)
		{
			in>>x;
		}
		if(cod==1)
		{
			first(x);
		}
		else if(cod==2)
			viz[x]=1;
		else if(cod==3)
		{
			third();
		}
	/*	for(int i=1;i<=len;i++)
			cout<<a[heap[i]]<<" ";
		cout<<endl;*/
	}
	return 0;
}