#include<iostream>
#include<string.h>
using namespace std;
const int N=1e5+10;
/*
heap[N]存放的是堆元素 
heap_sequence[N]存放的是索引为N的堆元素的插入顺序
sequence_heap[N]存放的是第N个插入堆的元素在堆中对应的索引
siz是当前堆大小
*/
int heap[N],heap_sequence[N],sequence_heap[N],siz;
void heap_swap(int index1,int index2)
{
    /*
    heap_sequence[index1]=在堆中索引为index1的元素的插入顺序
    heap[index1]=在堆中索引为index1的元素
    */
    swap(sequence_heap[heap_sequence[index1]],sequence_heap[heap_sequence[index2]]);
    swap(heap_sequence[index1],heap_sequence[index2]);
    swap(heap[index1],heap[index2]);
}
void down(int index)
{
    int m=index;
    if(2*index<=siz && heap[2*index]<heap[m]) m=2*index;
    if(2*index+1<=siz && heap[2*index+1]<heap[m]) m=2*index+1;
    if(m!=index)
    {
        heap_swap(index,m);
        down(m);
    }
}
void up(int index)
{
/*
若堆中索引为index的父节点存在 且 父节点对应的值>当前儿子节点
的值 交换两节点对应的相关值
*/
    if(index/2 && heap[index/2]>heap[index])
    {
        heap_swap(index,index/2);
        //递归处理
        up(index/2);
    }
}
int main()
{
    int n,m=0;
    scanf("%d",&n);
    while(n--)
    {
        char op[3];
        int k,x;
        scanf("%s",op);
        //cout<<op<<endl;
        if(op[0]=='D')
        {
            if(strlen(op)==2)//删除堆顶元素(最小值)
            {
                heap_swap(1,siz);
                siz--;
                down(1);
            }
            else//删除第k个插入的数
            {
                scanf("%d",&k);
                //sequence_heap[k]=第k个插入的数在堆中对应的
                //索引
                k=sequence_heap[k];
                heap_swap(k,siz);
                siz--;
                up(k);
                down(k);
            }
        }
        else if(op[0]=='I')//向推中插入一个数
        {
            scanf("%d",&x);
            siz++;
            m++;
            sequence_heap[m]=siz;
            heap_sequence[siz]=m;
            heap[siz]=x;
            up(siz);
        }
        else if(op[0]=='P')//输出堆顶元素(最小值)
            printf("%d\n",heap[1]);
        else//修改第k个插入的数
        {
            scanf("%d%d",&k,&x);
            k=sequence_heap[k];
            heap[k]=x;
            up(k);
            down(k);
        }
    }
    return 0;
}