#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])
	     s = crt*2;

	 if(s+1 <= n && h[crt] > h[s+1])
	     ++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)
	 {
	     h[ bagat[y] ] = -1;
	     up(bagat[y]);

	     bagat[poz[1]] = 0;
	     h[1] = h[n];
	     poz[1] = poz[n];
	     bagat[ poz[n] ] = 1;
	     --n;
	     if(n > 1)
		 down(1);

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

     }
     return 0;
}