#include <iostream>
#include <fstream>
#include <algorithm>

#define N 200005
#define inf 0x3f3f3f3f

using namespace std;

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

int n, x, e, nr, l, h[N], v[N], poz[N];

void push(int x)
{
	while(x/2 && v[h[x]] < v[h[x/2]])
	{
		swap(h[x], h[x/2]);
		
		poz[h[x]] = x;
		poz[h[x/2]] = x/2;
		
		x /= 2;
	}
}

void pop(int x)
{
	int y;
	while(x != y)
	{
		y = x;
		if(2*y <= l && v[h[x]] > v[h[y*2]]) x = y*2;
		if(2*y+1 <= l  && v[h[x]] > v[h[y*2+1]]) x = y*2+1;
		
		swap(h[x], h[y]);
		poz[h[x]] = x;
		poz[h[y]] = y;
	}
}

int main()
{
	fin>>n;
	for(int i=1; i<=n; ++i)
	{
		fin>>e;
		if(e == 1)
		{
			fin>>x;
			l++, nr++;
			
			poz[nr] = l;
			v[nr] = x; 
			h[l] = nr;
			
			push(l);
		}
		else if(e == 2)
		{
			fin>>x;
			v[x] = -1;
			push(poz[x]);
			
			poz[h[1]] = 0;
			h[1] = h[l--];
			poz[h[1]] = 1;
			
			if(l > 1) pop(1);
		}
		
		else
			fout<<v[h[1]]<<'\n';
	}
	return 0;
}