#include<stdio.h>
#include<algorithm>

using namespace std;

FILE *in, *out;

//definitions

//constants
const int sz = (int) 2e5+1;

//variables
int nOperations;
int type, value;

int heap[sz];
int appear[sz];
int position[sz];

int elem, lenght;

//functions
void insert(int pos);
void erase(int pos);

int main(void)
{
	in = fopen("heapuri.in", "rt");
	out = fopen("heapuri.out", "wt");
	
	fscanf(in,"%d", &nOperations);
	
	for(int i=1; i<=nOperations; ++i)
	{
		fscanf(in, "%d", &type);
		
		if(type == 1)
		{
			fscanf(in, "%d", &value);
			
			appear[++elem] = value;
			heap[++lenght] = elem;
			position[elem] = lenght;
			
			insert(lenght);
		}
		else if( type == 2)
		{
			fscanf(in, "%d", &value);
			
			appear[value] = -1;
			
			insert(position[value]);
			
			position[heap[1]] = 0;
			heap[1] = heap[lenght--];
			position[heap[1]] = 1;
			
			if(lenght > 0)
				erase(1);
		}
		else
			fprintf(out, "%d\n", appear[heap[1]]);
	}
	
	fclose(in);
	fclose(out);
	return 0;
}

void insert(int pos)
{
	int son = pos, father = son/2;
	
	while( father && appear[heap[son]] < appear[heap[father]] )
	{
		swap(heap[son], heap[father]);
		
		position[heap[son]] = son;
		position[heap[father]] = father;
		
		son = father;
		father /=2;
	}
}


void erase(int pos)
{
	int father = pos, y = 0, son = pos*2;
	
	while (father != son)
	{
		y = father;
		if( son <= lenght && appear[heap[father]] > appear[heap[son]])
			father = son;
		if( son+1 <= lenght && appear[heap[father]] > appear[heap[son+1]])
			father = son+1;
		
		swap(heap[father], heap[y]);
					
		position[heap[father]] = father;
		position[heap[y]] = y;
	}
}