# include <fstream>
# define  MAX  200100
  using namespace std;
    ifstream f ("heapuri.in");
	ofstream g ("heapuri.out");
    int n;
	int t[MAX], v[MAX], af[MAX];
	inline int dad (int son){
		return son >> 1;
	}
	inline int son1 (int dad){
		return dad << 1;
	}
	inline int son2 (int dad){
		return (dad << 1) + 1;
	}
	void HEAP (int poz, int nr){
		for (;;){
			int x = dad (poz), y = son2 (x);
			if (v[x] >= v[poz] && v[poz] <= v[y] && x > 0 && y > 0){//daca v[x] poate fi tata
				int aux = v[x];
				v[x] = v[poz];
				v[poz] = aux;
				//t[poz] = x;
				t[x] = poz;
				//t[x] = nr;//!!!!!!!!!!!!!!!!!!!!!!!!!
				t[nr] = x;
				poz = x;
			}
			else{
				break ;//nu mai poate inainta
			}
		}
	}
	void HEAP2 (int poz, int nr){
		for (;;){
			int x = son1 (poz), y = son2 (poz);
			if (v[x] <= v[y] && x <= v[0]){
				int aux = v[x];
			    v[x] = v[poz];
			    v[poz] = aux;
				
				int abc = t[nr];
				t[nr] = x;//al doilea intrat e pe poz x;
				t[poz] = abc;
				
				poz = x;
			}
			else
			if (v[x] > v[y] && y <= v[0]){
				int aux = v[y];
			    v[y] = v[poz];
			    v[poz] = aux;
				
				int abc = t[nr];
				t[nr] = y;//al doilea intrat e pe poz x;
				t[poz] = abc;
				
				
				poz = y;
			}
			else break ;
		}
	}
    int main (){
		f >> n;
		int cnt = 1;
		for (int i = 1; i <= n; ++i) v[i] = 1999999999;
		for (int i = 1; i <= n; ++i){
			int cit, nr;
			f >> cit;
			if (cit == 1){
				int var;
				f >> nr;
				v[++v[0]] = nr;
				//t[cnt] = v[0];
				t[v[0]] = cnt;
				HEAP (v[0], cnt);
				++cnt;
			}
			else
			if (cit == 2){
				f >> nr;
				int pozlast;
				//for (int j = 1; j <= n; ++j)
				//	if (v[j] == pozitie){
				//		pozlast = j;
				//		break ;
				//	}
				//pozlast = af[elem[nr]];
				pozlast = t[nr];
				v[pozlast] = 2000000000;
				HEAP2 (pozlast, nr);
			}
			else g << v[1] << '\n';
		}
		g.close ();
		return 0;
	}