#include<bits/stdc++.h>
using namespace std;
int n;
map<int,int> m;
int Read;
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++) {
		int p;
		scanf("%d%d",&p,&Read);
		switch(p) {
			case 1: {
				m[Read] ++;
				break;
			}
			case 2: {
				map<int,int>:: iterator it;
				if(m.empty()) {
					printf("Empty\n");
					continue;
				}
				if(m.find(Read) != m.end()) {
					m[Read] --;
					if(m[Read] == 0) 
						m.erase(Read);
					printf("%d\n",Read);
					continue;
 				}
 				m[Read] ++;
 				it = m.find(Read);
 				int l,r;
 				if(it == m.begin()) {
 					it ++;
 					printf("%d\n",it -> first);
 					it -> second --;
 					if(it -> second == 0) 
 						m.erase(it -> first);
 					m.erase(Read);
 					continue;
				}
				it ++;
				if(it == m.end()) {
					it --;
					it --;
					printf("%d\n",it -> first);
					it -> second --;
					if(it -> second == 0) 
						m.erase(it -> first);
					m.erase(Read);
					continue;
				}
				it --;
				it --;
				l = it -> first;
				it ++;
				it ++;
				r = it -> first;
				it --;
				if(abs(l - Read) <= abs(r - Read)) {
					it --;
					it -> second --;
					printf("%d\n",it -> first);
					if(it -> second == 0) 
						m.erase(it -> first);
					m.erase(Read);
				}else {
					it ++;
					it -> second --;
					printf("%d\n",it -> first);
					if(it -> second == 0) 
						m.erase(it -> first);
					m.erase(Read);
				
				}
				break;
			}
		}
		
	}
	

	return 0;
}