#include <fstream>

#define maxn 200001

using namespace std;

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

int N, L, NR;
int m[maxn], heap[maxn], pos[maxn];

void pop(int x)
{
	int swap;
    int y = 0;

	while (x != y) {

		y = x;

		if (y*2<=L && m[heap[x]]>m[heap[y*2]]) {
            x = y*2;
        }

		if (y*2+1<=L && m[heap[x]]>m[heap[y*2+1]]){ 
            x = y*2+1;
        }

		swap = heap[y];
		heap[y] = heap[x];
		heap[x] = swap;

		pos[heap[x]] = x;
		pos[heap[y]] = y;
	}
}

void push(int x)
{
    int swap;
	while (x/2 && m[heap[x]]<m[heap[x/2]]) {

		swap = heap[x/2];
		heap[x/2] = heap[x];
		heap[x] = swap;

		pos[heap[x]] = x;
		pos[heap[x/2]] = x/2;
		x = x / 2;
	}
}


int main() {

	int i, x;
    int test;

	fin >> N;

	for (i=1; i<=N; i++)
	{
		fin >> test;

		if (test < 3) {
			fin >> x;
		}

        switch(test){
            case 1:
                L++, NR++;
                m[NR] = x;
                heap[L] = NR;
                pos[NR] = L;

                push(L);
                break;
            
            case 2:
                m[x] = -1;
                push(pos[x]);

                pos[heap[1]] = 0;
                heap[1] = heap[L--];
                pos[heap[1]] = 1;

                if (L>1) { 
                    pop(1);
                }
            break;

            case 3:
                fout << m[heap[1]] << endl;
                break;

            default:
                break;

        }
	}

	return 0;
}