#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<set>
using namespace std;
stack<int> st;
//本题采用平衡二叉树来实现对顶堆的思想解决此题
//再编写的时候始终维护down比up要多一个或者两者数量相同
//up是较大的那一半,down是较小的那一半
multiset<int> up,down;
void change(){
    //需要改变的情况为up比down多,或者down-up>1
    while(up.size()>down.size()){
        auto t = up.begin();
        down.insert(*t);
        up.erase(t);
    }
    while(down.size()-up.size()>1){
        auto t = down.end();t--;
        up.insert(*t);down.erase(t);
    }
}
int main(){
    int n;string s;
    scanf("%d\n",&n);
    while(n--){
        getline(cin,s);
        if(s=="Pop"){
            if(st.empty()) printf("Invalid\n");
            else{
                int k = st.top();st.pop();
                printf("%d\n",k);
                auto t = down.end();t--;
                //这个时候我们需要找到k这个值并把它删除掉
                if(k<=*t){
                    //说明k一定是在down中,但是在up里面不一定有
                    down.erase(down.find(k));//这里不能直接写k不然会把
                    //down里面的k全删掉,但是如果写find就只删除一个
                }else{
                    up.erase(up.find(k));
                }
                change();
            }
        }else if(s=="PeekMedian"){
            if(st.empty()) printf("Invalid\n");
            else{
                auto t = down.end();
                t--;printf("%d\n",*t);
            }
        }else{
            int k = stoi(s.substr(5));
            st.push(k);
            //push之后需要考虑将k插入到up还是down中
            //为什么不能随便插入到up与down然后直接change来调整呢?
            //因为这样可能会破坏有序性,比如一直插入到up的话,
            //刚好此时up比down少一个,这时直接插入一个很小的数到up中
            //不会调整,这就错了,同理,比如一直插入到down,假如此时up与
            //down相等,那么这时插入一个很大的数,就直接到down中不调整了
            //这就错了
            //因此在插入时我们一定要保证总体上时有序的
            if(up.empty() || k<=*up.begin()) down.insert(k);
            else up.insert(k);
            change();
        }
    }
}