#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N = 1e5 + 10;

int n,m;
int size;
int h[N];

//需要從第幾個(gè)插入的點(diǎn)里邊找到我們的元素,又需要堆里邊的元素找回去,找到是第幾個(gè)插入的
//也就是第k個(gè)插入的點(diǎn)和堆里邊的元素的映射

//表示第K個(gè)插入的下標(biāo)是什么是哪一個(gè)點(diǎn)
int ph[N];

//表示堆里面的點(diǎn)是第幾個(gè)插入的點(diǎn)
int hp[N];

//具有映射的交換操作
void heap_swap(int a,int b){
    
    //下面幾個(gè)操作保證交換插入元素值之后的附加插入下標(biāo)屬性不變
    //也就是保證插入元素后,記錄跟隨第幾個(gè)插入的下標(biāo)元素不會(huì)變
    
    //交換第幾個(gè)插入的下標(biāo)的值
    swap(ph[hp[a]],ph[hp[b]]);
    
    //交換第幾個(gè)插入點(diǎn)的下標(biāo)
    swap(hp[a],hp[b]);
    
    //值進(jìn)行交換
    swap(h[a],h[b]);
}

void down(int u){
    int t = u;
    if(u*2 <= size && h[u*2] < h[t]) t = u*2;
    if(u*2 + 1 <= size && h[u*2 + 1] < h[t]) t = u*2+1;
    if(t!=u){
        heap_swap(u,t);
        down(t);
    }
}

void up(int u){
    while(u / 2 && h[u/2] > h[u]){
        heap_swap(u/2,u);
        u /= 2;
    }
}

int main(){
  //初始化m記錄當(dāng)前是第幾個(gè)插入的數(shù)
  int n,m = 0;
  scanf("%d",&n);
  
  while(n --){
      char op[10];
      
      int k,x;
      
      scanf("%s",op);
      //strcmp是<string.h>庫的一個(gè)比較字符串的函數(shù),如果相同就等于0
      if(!strcmp(op,"I")){
        scanf("%d",&x);
        size++;//堆里邊多一個(gè)元素
        m++;
        
        //一開始堆里邊的第m個(gè)插入元素就是在size這個(gè)位置
        ph[m] = size;
        //一開始堆里邊size這個(gè)位置上的數(shù)是第m個(gè)插入進(jìn)來的
        hp[size] = m;
        //當(dāng)然也需要在堆中的size的位置上添加元素
        h[size] = x;
        up(size);//將元素向上懟
      }
      else if(!strcmp(op,"PM")) printf("%d\n",h[1]);
      else if(!strcmp(op,"DM")) 
      {
          heap_swap(1,size);
          size -- ;
          down(1);
      }
      else if(!strcmp(op,"D")){
          scanf("%d",&k);
          //將第k個(gè)元素是第幾個(gè)插入的取出來
          k = ph[k];
          heap_swap(k,size);
          size -- ;
          down(k),up(k);
      }
      else{
          scanf("%d%d",&k,&x);
          //拿出第k個(gè)要插入的元素
          k = ph[k];
          h[k] = x;
          down(k);
          up(k);
      }
  }
  
  return 0;
}