#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=3e5+6;
int n , ar[MX], guid[MX];
char bb[MX];int NN;
struct State
{
    ll data;
    ll i;
    State()
    {
        data=0,i=0;
    };
    State(ll a,int c)
    {
        data=a;
        i=c;
    }
};
bool operator<(const State x,const State y)
{
    if(x.data<y.data)return 1;
    return 0;
}
int id;
int easy[4*MX];
void insrt(int x=1,int l=0,int r=NN)
{
    int mid=(l+r)/2;
    if(l==r&&r==id)
    {
        easy[x]++;return;
    }
    if(l<=id&&id<=mid)
    {
        insrt(2*x,l,mid);
        easy[2*x+1]++;
    }
    else if(mid<id&&r>=id)
    {
        insrt(2*x+1,mid+1,r);
    }
}
int getnum(int x=1,int l=0,int r=NN)
{
    int mid=(l+r)/2;
    if(l==r&&r==id)
    {
        return easy[x];
    }
    if(l<=id&&id<=mid)
    {
        return getnum(2*x,l,mid)+ easy[x];
    }
    else if(mid<id&&r>=id)
    {
        return getnum(2*x+1,mid+1,r)+ easy[x];
    }
    return 0;
}
void kill(int x=1,int l=0,int r=NN)
{
    int mid=(l+r)/2;
    if(l==r&&r==id)
    {
        easy[x]--;
        return;
    }
    if(l<=id&&id<=mid)
    {
        easy[2*x+1]--;
        kill(2*x,l,mid);
    }
    else if(mid<id&&r>=id)
    {
        kill(2*x+1,mid+1,r);
    }
}
vector<State> vr;
multiset<int> mst;
int countheap(int x)
{
    int st=0,en=(int)vr.size() -1,num=0;
    ll opt=-1e10;
    while(st<=en)
    {
        id =(st+en)/2;
        if(vr[id].data<x)
        {
            if(opt<=vr[id].data)
            {
                opt=vr[id].data;
                num=id+1;
            }
            st=id+1;
        }else en=id-1;
    }
    id=num-1;
    return getnum();
}
int KTH(int k)
{
     int st=0,en=(int)vr.size()-1;
     int opt=(int)vr.size()+1;
        while(st<=en)
            {
                id=(st+en)/2;
                if(getnum()>=k)
                {
                    opt=min(id,opt);
                    en=id-1;
                }else st=id+1;
            }
        return opt;
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
       {
          scanf(" %c%d",&bb[i],&ar[i]);
          if(bb[i]=='I')vr.push_back({ar[i],i});
       }
     sort(vr.begin(),vr.end());
     NN=(int)vr.size() -1;
     for(int i=0;i<vr.size();i++)
        guid[vr[i].i]=i;
    for(int i=1;i<=n;i++)
    {
        if(bb[i]=='I')
        {
            if(mst.count(ar[i]))continue;
            id=guid[i];
            insrt();
            mst.insert(ar[i]);
        }
        if(bb[i]=='D')
        {
            if(!mst.count(ar[i]))continue;
            id=guid[i];
            mst.erase(mst.find(ar[i]));
            kill();
        }
        if(bb[i]=='C')
        {
            printf("%d\n",countheap(ar[i]));
        }
        if(bb[i]=='K')
        {
            int cur=KTH(ar[i]);
            if(cur>=vr.size())printf("invalid\n");
            else printf("%d\n",vr[cur].data);
        }
    }

    return 0;

}