#include <iostream>
//#include "optimization.h"
using namespace std;
int hmax[100001], hmin[100001], delmin[100001], delmax[100001];
int n1 = 0, n2 = 0, n3 = 0, n4 = 0;
int i, l = 2*i;
int countmin, countmax;

int GetMin_hmin() {
	return hmin[1];
}
int GetMin_delmax() { return delmax[1]; }
int GetMax_hmax() { return hmax[1]; }
int GetMax_delmin() { return delmin[1]; }

void siftDown_hmax(int i) {
	while (1) {
		if (l + 1 <= n1 && hmax[l + 1] > hmax[l])
			l++;
		if (l >= n1 && hmax[l] < hmax[i])
			break;
		swap(hmax[l], hmax[i]);
		i = l;
	}
}
void siftDown_hmin(int i) {
	while (1) {
		//int l = 2 * i;
		if (l + 1 <= n2 && hmin[l + 1] < hmin[l]) l++;
		if (!(l <= n2 && hmin[l] < hmin[i])) break;
		swap(hmin[l], hmin[i]);
		i = l;
	}
}
void siftDown_delmin(int i) {
	while (1) {
		int l = 2 * i;
		if (l + 1 <= n3 && delmin[l + 1] > delmin[l]) l++;
		if (!(l <= n3 && delmin[l] > delmin[i])) break;
		swap(delmin[l], delmin[i]);
		i = l;
	}
}
void siftDown_delmax(int i) {
	while (1) {
		//int l = 2 * i;
		if (l + 1 <= n4 && delmax[l + 1] < delmax[l]) l++;
		if (!(l <= n4 && delmax[l] < delmax[i])) break;
		swap(delmax[l], delmax[i]);
		i = l;
	}
}
void ExtractMin_hmin() {
	swap(hmin[1], hmin[n2--]);
	siftDown_hmin(1);
}
void ExtractMin_delmax() {
	swap(delmax[1], delmax[n4--]);
	siftDown_delmax(1);
}
void ExtractMax_hmax() {
	swap(hmax[1], hmax[n1--]);
	siftDown_hmax(1);
}
void ExtractMax_delmin() {
	swap(delmin[1], delmin[n3--]);
	siftDown_delmin(1);
}

void siftUp_hmin(int i) {
	while (i > 1 && hmin[i / 2] > hmin[i]) {
		swap(hmin[i], hmin[i / 2]);
		i /= 2;
	}
}
void siftUp_hmax(int i) {
	while (i > 1 && hmax[i / 2] < hmax[i]) {
		swap(hmax[i], hmax[i / 2]);
		i /= 2;
	}
}
void siftUp_delmax(int i) {
	while (i > 1 && delmax[i / 2] > delmax[i]) {
		swap(delmax[i], delmax[i / 2]);
		i /= 2;
	}
}
void siftUp_delmin(int i) {
	while (i > 1 && delmin[i / 2] < delmin[i]) {
		swap(delmin[i], delmin[i / 2]);
		i /= 2;
	}
}

void Add_delmax(int x) {
	delmax[++n4] = x;
	siftUp_delmax(n4);
}
void Add_delmin(int x) {
	delmin[++n3] = x;
	siftUp_delmin(n3);
}

int GetMax() {
	if (countmin) {
		while (GetMax_hmax() == GetMax_delmin()) {
			ExtractMax_hmax();
			ExtractMax_delmin();
			countmin--;
			if (!countmin) break;
		}
	}
	int x = GetMax_hmax();
	Add_delmax(x);
	countmax++;
	ExtractMax_hmax();
	return x;
}
int GetMin() {
	if (countmax) {
		while (GetMin_hmin() == GetMin_delmax()) {
			ExtractMin_hmin();
			ExtractMin_delmax();
			countmax--;
			if (!countmax) break;
		}
	}
	int x = GetMin_hmin();
	Add_delmin(x);
	countmin++;
	ExtractMin_hmin();
	return x;
}

void Add(int x) {
	hmax[++n1] = x;
	siftUp_hmax(n1);
	hmin[++n2] = x;
	siftUp_hmin(n2);
}

int main() {
	int n;
	cin >> n; //n = readInt();
	char input[30];
	for (int j = 0; j < n; j++) {
		int i = 0;
		cin >> input[i]; // = readChar();
		int num;
		if (input[i] == 'I') {
			while (input[i] != '(') {
				i++;
				cin >> input[i]; // = readChar();
			}
			i++;
			cin >> input[i]; // = readChar();
			num = 0;
			while (input[i] != ')') {
				num *= 10;
				num += input[i] - '0';
				cin >> input[i]; // = readChar();
			}
			Add(num);
		}
		else {
			while (input[i] != 'M') {
				i++;
				cin >> input[i]; // = readChar();
			}
			i++;
			cin >> input[i]; // = readChar();
			if (input[i] == 'a') {
				cin >> input[i]; // = readChar();
				cout << GetMax() << '\n';
			}
			else {
				cin >> input[i]; // = readChar();
				cout << GetMin() << '\n';
			}
		}
	}
	return 0;
}