/*维护一个集合，初始时集合为空，支持如下几种操作：
“I x”，插入一个数x；
“PM”，输出当前集合中的最小值；
“DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）；
“D k”，删除第k个插入的数；
“C k x”，修改第k个插入的数，将其变为x；
现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。
输入格式：
第一行包含整数N。
接下来N行，每行包含一个操作指令，操作指令为”I x”，”PM”，”DM”，”D k”或”C k x”中的一种。
输出格式：
对于每个输出指令“PM”，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围：
1≤N≤105
-109≤x≤109
数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
注意：1.插入一个数：heap[++size]=x,up(size);
2.求集合当中最小值：heap[1];
3.删除最小值：heap[1]=heap[size],size--,down(1);
4.删除任意一个元素：heap[k]=heap[size],size--,down(k),up(k);
5.修改任意一个元素：heap[k]=x,down(k),up(k);
6.siz为当前集合的大小，m表示总共插入几个元素
7.ph[]为指针指向堆，hp[]为堆指向指针
*/
//code：
#include<iostream>
using namespace std;
const int N=1e5+10;
int h[N],ph[N],hp[N],n,siz,x,k,m;
char s[5];
void swap_h(int a,int b)//构建堆独特交换方式
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void down(int x)//下沉
{
int t=x;
if(2*x<=siz&&h[2*x]<h[t]) t=2*x;
if(2*x+1<=siz&&h[2*x+1]<h[t]) t=2*x+1;
if(t!=x)
{
swap_h(t,x);
down(t);
}
}
void up(int x)//上浮
{
while(x/2>0&&h[x/2]>h[x])
{
swap_h(x/2,x);
x/=2;
}
}
int main()
{
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
if(s[0]=='I')//插入一个数
{
scanf("%d",&x);
siz++;//当前集合的元素个数
m++;//记录插入第几个元素
ph[m]=siz;//prime->heap ：指针指向堆
hp[siz]=m;//heap->prime ：堆指向指针
h[siz]=x;//下标size后插入元素x
up(siz);//对插入元素进行上浮操作，维护小根堆
}
else if(s[0]=='P')//输出当前集合的最小值
{
printf("%d\n",h[1]);
}
else if(s[1]=='M')//删除当前集合的最小值
{
swap_h(1,siz);//用最后一号元素覆盖一号元素
siz--;//进行siz--操作，去除重复的最后一号元素
down(1);//再对临时根节点进行下沉操作，维护小根堆
}
else if(s[0]=='D')//删除第k个插入的数
{
scanf("%d",&k);
k=ph[k];//询问第k个插入元素在当前集合的下标
swap_h(k,siz);//先覆盖
siz--;//再删除
down(k),up(k);//然后down，up
}
else//修改第k个插入的数，将其变为x
{
scanf("%d%d",&k,&x);
k=ph[k];//询问第k个插入元素在当前集合的下标
h[k]=x;//修改元素
down(k),up(k);//down，up
}
}
return 0;
}