#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int cnt;    //记录的是堆当前的数据多少
int h[N];   //堆
int ph[N];  //存放第k个插入点的下标
int hp[N];  //存放堆中点的插入次序
void heap_swap(int a,int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}
//之所以要进行这样的操作是需要因为经过一系列操作 堆中的元素并不会保持原有的插入顺序
//需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void down(int u)
{
    int t=u;
    if(2*u<=cnt&&h[2*u]<h[t])
        t=2*u;
    if(2*u+1<=cnt&&h[2*u+1]<h[t])
        t=2*u+1;
    if(t!=u)
    {
        heap_swap(u,t);
        down(t);
    }
}
void up(int u)
{
    while(u/2&&h[u]<h[u/2])
    {
        heap_swap(u,u/2);
        u/=2;
    }
}
int main()
{
    int n,m=0;
    //m用来记录插入的数的个数
    //注意m的意义与cnt是不同的 cnt是记录堆中当前数据的多少
    //对应上文 m即是hp中应该存的值
    cin>>n;
    while(n--)
    {
        string op;
        cin>>op;
        int k,x;
        if(op=="I")
        {
            scanf("%d", &x);
            cnt ++ ;
            m ++ ;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if(op=="PM")
        {
            cout<<h[1]<<endl;
        }
        else if(op=="DM")
        {
            heap_swap(1,cnt);                                           
            cnt--;                                            
            down(1);                                            
        }
        else if(op=="D")
        {
            cin>>k;
            k=ph[k];
            heap_swap(k,cnt);
            cnt--;

            down(k);
            up(k);
        }
        else
        {
            cin>>k>>x;
            k=ph[k];
            h[k]=x;

            down(k);
            up(k);
        }
    }
    return 0;
}