#include<cstdio>
#include<string>
#include<iostream>
#include<stack>
#include<set>
using namespace std;
int n;
int main()
{
cin>>n;
stack<int> s;
multiset<int> order;
int key;
for(int i = 0; i < n; i++)
{
string ope;
cin>>ope;
if(ope == "Push")
{
cin>>key;
s.push(key);
order.insert(key);
}
else if(ope == "Pop" && !s.empty())
{
int val = s.top();
cout<<val<<endl;
s.pop();
order.erase(val);
}
else if(ope == "PeekMedian")
{
if(order.empty())
cout<<"Invalid"<<endl;
else
{
int num = s.size();
num = (num%2 == 0)? num/2 : (num+1)/2;
auto it = order.begin();
cout<<(*it+num-1)<<endl;
}
}
else
{
cout<<"Invalid"<<endl;
}
}
return 0;
}