#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=1e5+19;
int h[N],ph[N],hp[N],num;
//ph 第k个插入点在堆的下标   hp  堆中的元素是第几个插入的数    ph[j]=k   hp[k]=j


void heap_swap(int a,int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}


void up(int u)
{
    while(u/2&&h[u/2]>h[u])
    {
        heap_swap(u/2,u);
        u/=2;
    }
}
void down(int u)
{
    int t=u;
    if(2*u<=num&&h[t]>h[u*2])t=2*u;
    if(2*u+1<=num&&h[t]>h[u*2+1])t=2*u+1;
    if(u!=t){
        heap_swap(u,t);
        down(t);
    }
}
int main()
{
    int n,m=0;
    scanf("%d",&n);
    while(n--)
   {
       string s;
       cin>>s;
       int x;int k;
       if(s=="I"){
           cin>>x;
           ++num;
           m++;ph[m]=num;hp[num]=m;h[num]=x;
           up(num);
       }
       else if(s=="PM")
       {
           printf("%d\n",h[1]);
       }
       else if(s=="DM")
       { 
           heap_swap(1,num);
           num--;
           down(1);

       }
       else if(s=="D")
       {
           cin>>k;
           k=ph[k];
           heap_swap(k,num);
           num--;up(k);
           down(k);
       }
       else if(s=="C")
       {   

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

       }
   }

    return 0;
}