#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
const int MAX = 100001;
const int MAXN = 317;
int n, block[MAXN] = {0}, table[MAX] = {0};
char order[11];
stack<int> s;
 
bool cmp(int a, int b){
	return a < b;
}
 
int main(){
	scanf("%d", &n);
	while(n--){
		scanf("%s", order);
		if(strcmp(order, "Pop") == 0){
			if(!s.empty()){
				int k = s.top();
				printf("%d\n", k);
				s.pop();
				block[k/(MAXN-1)]--;
				table[k]--;
			}else printf("Invalid\n");
		}else if(strcmp(order, "PeekMedian") == 0){
			if(s.empty()){
				printf("Invalid\n");
				continue;
			}
			int k, idx = 0, index = 0;
			if(s.size() % 2 == 0) k = s.size()/2;
			else k = (s.size()+1)/2;
			int sum = 0;
			while(sum + block[idx] < k){
				sum += block[idx++];
			}
			index = idx * (MAXN-1);
			while(sum + table[index] < k){
				sum += table[index++];
			}
			printf("%d\n", index);
		}else{
			int k;
			scanf("%d", &k); 
			s.push(k);
			table[k]++;
			block[k/(MAXN-1)]++;
		}
	}
	return 0;
}