#include <stdio.h>
#define MAXN 200010
void pop(int x);
void push(long x);
int n, iheap, ia, a[MAXN], heap[MAXN], poz[MAXN];
int main()
{
	int i, cod, x;
	freopen("heapuri.in", "r", stdin);
	freopen("heapuri.out", "w", stdout);
	scanf("%d", &n);
	for (i=1; i<=n; i++)
	{
		scanf("%d", &cod);
		if (cod<3)
		{
			scanf("%d", &x);
			if (cod==1)
			{
				a[++ia]=x;
				heap[++iheap]=ia;
				poz[ia]=iheap;
				push(iheap);
			}//if
			else
				if (cod==2)
				{
					a[x]=-1;
					push(poz[x]);
					poz[heap[1]]=0;
					heap[1]=heap[iheap--];
					poz[heap[1]]=1;
					if (iheap>1)
						pop(1);
				}//if
		}//if
		else
			printf("%d\n", a[heap[1]]);
	}//for i
	return 0;
}//main

void pop(int x)
{
	int aux, y;
	y=0;
	while (x!=y)
	{
		y=x;
		if (y*2<=iheap && a[heap[x]]>a[heap[y*2]])
			x=y*2;
		if (y*2+1<=iheap && 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;
	}//while
}//pop

void push(long 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/=2;
  }//while
}//push