// http://infoarena.ro/problema/heapuri

#include <stdio.h>
#include <stdlib.h>

#define NMAX 200005

int A[NMAX], // valorile efective ale nodurilor
    Heap[NMAX], // heapul, unde fiecare valoare este numarul de ordine al unei valori, Pos 
    Pos[NMAX]; // pozitia in heap a unui nod

int n = 0, // numarul de noduri din heap
    numIns = 0; // numarul de noduri inserate

inline int cmp(int a, int b) {
	return A[a] < A[b]; // asta e relatia care ar trebui respectata intre parinte si copii
}

void swap(int *a, int *b) {
	int c = *a;
	*a = *b;
	*b = c;
}

void swim(int p) {
	while (p / 2 >= 1 && !cmp(Heap[p / 2], Heap[p])) {
		swap(&Heap[p], &Heap[p / 2]);
		swap(&Pos[Heap[p]], &Pos[Heap[p / 2]]);
		p /= 2;
	}
	Pos[Heap[p]] = p;
}

void sink(int p) {
	int j;
	while (2 * p <= n) {
		j = 2 * p;
		if (j + 1 <= n && !cmp(Heap[j], Heap[j + 1]))
			++ j;
		if (!cmp(Heap[p], Heap[j])) {
			swap(&Heap[p], &Heap[j]);
			swap(&Pos[Heap[p]], &Pos[Heap[j]]);
			p = j;
		} else
			break;
	}
}

int main() {
	FILE *in = fopen("heapuri.in", "r"),
	     *out = fopen("heapuri.out", "w");
	int t, type, val;

	for(fscanf(in, "%d", &t); t > 0; -- t) {
		fscanf(in, "%d", &type);
		if (type != 3)
			fscanf(in, "%d", &val);
		switch (type) {
			case 1:
				A[numIns] = val;
				Heap[++ n] = numIns;
				Pos[numIns] = n;
				swim(n);
				++ numIns;
				break;
			case 2:
				A[val - 1] = -1;
				Pos[Heap[n]] = Pos[val - 1];			
				swap(&Heap[n], &Heap[Pos[val - 1]]);
				-- n;
				sink(Pos[val - 1]);
				break;
			case 3:
				fprintf(out, "%d\n", A[Heap[1]]);
				break;
		}
	}

	fclose(in);
	return 0;
}