//这题难道不需要建堆的吗,题目要求是初始为空
//strcmp函数是string compare(字符串比较)的缩写,用于比较两个字符串并根据比较结果返回整数。
//基本形式为strcmp(str1,str2),若str1=str2,则返回零;
//若str1<str2,则返回负数;若str1>str2,则返回正数。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int h[N],siz;//全局变量放在静态存储区,c和c++都是设初值为0,如果是局部变量的话不会赋初值,
//只是把一块地址给你,至于里面是什么就不知道了。
int ph[N],hp[N];
//为实现op4.5所必须的堆交换
void heap_swap(int a,int b)
{
//其实就是所有的都要交换一次,无论是ph还是hp还是值
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
//下沉
void down(int u)
{
int t = u;//可以理解t为指向小型堆中min的指针
if(2*u <= siz && h[2*u] <h[t]) t = 2*u;
if(2*u+1 <= siz && h[2*u+1] <h[t]) t = 2*u+1;
if(t != u)
{
heap_swap(t,u);
down(t);//t指向了不是根的位置,需要考虑换位之后对另一个堆的影响
//所以需要down(t),让它去递归
}
}
//上浮
void up(int u)
{
while(u/2 && h[u] < h[u/2])//while只要符合条件就递归
{
heap_swap(u, u/2);
u /=2;
}
}
int main()
{
int n,m = 0;
scanf("%d",&n);
while(n--)
{
char op[5];
int k,x;
scanf("%s",op);
if(!strcmp(op,"I"))
{
cin>>x;
siz++;//堆容量++
m++;//插入的数计数
ph[m] = siz,hp[siz] = m;//加入映射关系
h[siz] = x;
up(siz);//插入数要保持堆平衡
}
else if(!strcmp(op,"PM"))
{
printf("%d\n",h[1]);
}
else if(!strcmp(op,"DM"))
{
//h[1] = h[siz]和swap(h[1],h[siz])没区别,所以其实删除的话
//siz那个位置上的数是原本的h【size】还是h【1】不重要,因为要被删除了
heap_swap(1,siz);
siz--;//为啥给的删除min不是这样的,这个题就要这样
down(1);
}
else if(!strcmp(op,"D"))
{
scanf("%d",&k);
k = ph[k];
heap_swap(k,siz);//h[k] = h[siz],heap_swap(k,size)同上
siz--;
down(k),up(k);
}
else
{
scanf("%d%d",&k,&x);
k = ph[k];
h[k] = x;
down(k),up(k);
}
}
return 0;
}