#include<cstdio>
#include<queue>
#include<set>
using std::priority_queue;
using std::multiset;

priority_queue<int> q;
int v[200005],nr;
multiset<int> dels;

int main()
{
	freopen ("heapuri.in","r",stdin);
	freopen ("heapuri.out","w",stdout);
	int n;
	scanf ("%d",&n);
	while(n--){
		int op;
		scanf ("%d",&op);

		int x;
		switch(op){
		case 1:
			scanf ("%d",&x);
			q.push (-x);
			v[nr++]=-x;
			break;

		case 2:
			scanf ("%d",&x);
			x=v[x-1];
			if(q.top()==x){//root was deleted
				q.pop();
				multiset<int>::iterator it=dels.find (q.top());
				while(it!=dels.end()){
					q.pop();
					dels.erase (it);
					it=dels.find(q.top());
				}
			} else //store deletion
				dels.insert (x);
			break;

		case 3:
			printf ("%d\n",-q.top());
		}
	}
	return 0;
}