#include <stdio.h>

#define NMAX 200010


int t, n;
int h[NMAX];
int poz[NMAX];
int nr;
int bagat[NMAX];

inline void hreverse(int x, int y)
{
	int aux;
	aux = h[x];
	h[x] = h[y];
	h[y] = aux;
}

inline void pozreverse(int x, int y)
{
	int aux;
	aux = poz[x];
	poz[x] = poz[y];
	poz[y] = aux;
}

inline void bagatreverse(int x, int y)
{
	int aux;
	aux = bagat[x];
	bagat[x] = bagat[y];
	bagat[y] = aux;
}

void up(int crt)
{
	int f;
	while(crt != 1)
	{
		f = crt/2;
		if(h[f] > h[crt])
		{
			bagatreverse(poz[crt], poz[f]);
			hreverse(crt, f);
			pozreverse(crt, f);
			crt = f;
		}
		else
			break;
	}
}

void down(int crt)
{
	int s;
	while(2*crt <= n)
	{
		s = crt*2;
		if(h[crt] > h[s])
		{
			bagatreverse(poz[crt], poz[s]);
			hreverse(crt, s);
			pozreverse(crt, s);
			crt = s;
			continue;
		}
		if(s+1 <= n)
			++s;

		if(h[crt] > h[s])
		{
			bagatreverse(poz[crt], poz[s]);
			hreverse(crt, s);
			pozreverse(crt, s);
			crt = s;
			continue;
		}
		else
			break;
	}
}

int main()
{
	int x, y, z;
	freopen("heapuri.in", "r", stdin);
	freopen("heapuri.out", "w", stdout);

	scanf("%d", &t);

	while(t--)
	{
		scanf("%d", &x);
		if(x != 3)
			scanf("%d", &y);

		if(x == 1)
		{
			bagat[++nr] = ++n;
			poz[n] = nr;
			h[n] = y;
			up(n);
		}
		else if(x == 2)
		{
			z = bagat[y];
			hreverse(n, bagat[y]);
			pozreverse(n, bagat[y]);
			bagatreverse(poz[n], bagat[y]);

			--n;
			down(z);
		}
		else
		{
			printf("%d\n", h[1]);
		}

	}
	return 0;
}