/*And I thought my jokes were bad*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define dbg puts("Viva la vida");
#define CHECK(x) cout << (#x) << " is " << (x) << endl;
#define nl puts("");
typedef map<int,int> mii;
typedef map<string,int> msi;
typedef pair<int,int> pii;
typedef pair<int,pii > tii;
typedef vector <int> VI;
typedef vector<ll> VL;
typedef set<int> SI;
#define mp make_pair
#define pb push_back
#define IN(x) scanf("%d",&x);
#define INL(x) scanf("%lld",&x);
#define OUT(x) printf("%d",x);
#define OUTL(x) printf("%lld",x);
#define SP printf(" ");
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define EPS 1e-9
#define PI acos(-1.0)
#define MAX 200005
#define MOD 1000000007
#define INF (1 << 31)
/*
Like memories in cold decay
Transmissions echoing away
Far from the world of you and I
Where oceans bleed into the sky
*/
vector<int> sh;
vector<pii > viva;
int tree[3*MAX];
map<int,int> ind,cntr;
void update(int n,int l,int r,int i,int v)
{
if(i>r)
return ;
if(i<l)
return ;
if(l==r&&l==i)
{
tree[n]=v;
return ;
}
int mid=l+r;
mid/=2;
update(2*n,l,mid,i,v);
update(2*n+1,mid+1,r,i,v);
tree[n]=tree[2*n]+tree[2*n+1];
return ;
}
int query(int n,int l,int r,int i,int j)
{
// cout<<i<<' '<<j<<endl;
if(i>r||j<l)
return 0;
if(i<=l&&j>=r)
return tree[n];
int mid=l+r;
mid/=2;
return query(2*n,l,mid,i,j)+query(2*n+1,mid+1,r,i,j);
}
int query_2(int n,int l,int r,int val)
{
// cout<<l<<' '<<r<<' '<<val<<endl;
if(tree[n]<val)
return -1;
if(l==r)
{
return l;
}
int mid=l+r;
mid/=2;
if(tree[2*n]>=val)
return query_2(2*n,l,mid,val);
else
return query_2(2*n+1,mid+1,r,val-tree[2*n]);
}
int main()
{
int i,j,k,n,m,p,q,t,x,y;
char ch;
cin>>n;
for (i=0;i<n;i++)
{
cin>>ch>>x;
viva.pb(mp(ch,x));
sh.pb(x);
}
unique(sh.begin(),sh.end());
sort(sh.begin(),sh.end());
for (i=0;i<sh.size();i++)
{
ind[sh[i]]=i;
}
for (i=0;i<n;i++)
{
ch=viva[i].first;
x=viva[i].second;
if(ch=='I')
{
// cout<<"INSERT"<<endl;
// CHECK(x)
// CHECK(ind[x]);
if(!cntr[x])
{
update(1,0,n,ind[x],1);
cntr[x]++;
}
}
else if(ch=='D')
{
if(cntr[x])
{
update(1,0,n,ind[x],0);
}
}
else if(ch=='C')
{
cout<<query(1,0,n,0,ind[x]-1)<<endl;
}
else if(ch=='K')
{
k=query_2(1,0,n,x);
if(~k)
cout<<sh[k]<<endl;
else
cout<<"invalid"<<endl;
}
}
return 0;
}
LypBbmQgSSB0aG91Z2h0IG15IGpva2VzIHdlcmUgYmFkKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGRiZyBwdXRzKCJWaXZhIGxhIHZpZGEiKTsKI2RlZmluZSBDSEVDSyh4KSBjb3V0IDw8ICgjeCkgPDwgIiBpcyAiIDw8ICh4KSA8PCBlbmRsOwojZGVmaW5lIG5sIHB1dHMoIiIpOwp0eXBlZGVmIG1hcDxpbnQsaW50PiBtaWk7CnR5cGVkZWYgbWFwPHN0cmluZyxpbnQ+IG1zaTsKdHlwZWRlZiBwYWlyPGludCxpbnQ+IHBpaTsKdHlwZWRlZiBwYWlyPGludCxwaWkgPiB0aWk7CnR5cGVkZWYgdmVjdG9yIDxpbnQ+IFZJOwp0eXBlZGVmIHZlY3RvcjxsbD4gVkw7CnR5cGVkZWYgc2V0PGludD4gU0k7CiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgSU4oeCkgc2NhbmYoIiVkIiwmeCk7CiNkZWZpbmUgSU5MKHgpIHNjYW5mKCIlbGxkIiwmeCk7CiNkZWZpbmUgT1VUKHgpIHByaW50ZigiJWQiLHgpOwojZGVmaW5lIE9VVEwoeCkgcHJpbnRmKCIlbGxkIix4KTsKI2RlZmluZSBTUCBwcmludGYoIiAiKTsKI2RlZmluZSBYIGZpcnN0CiNkZWZpbmUgWSBzZWNvbmQKI2RlZmluZSBTWihfYSkgKGludClfYS5zaXplKCkKI2RlZmluZSBBTEwoX2EpIF9hLmJlZ2luKCksX2EuZW5kKCkKI2RlZmluZSBFUFMgMWUtOQojZGVmaW5lIFBJIGFjb3MoLTEuMCkKI2RlZmluZSBNQVggMjAwMDA1CiNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKI2RlZmluZSBJTkYgKDEgPDwgMzEpCgovKgpMaWtlIG1lbW9yaWVzIGluIGNvbGQgZGVjYXkKVHJhbnNtaXNzaW9ucyBlY2hvaW5nIGF3YXkKRmFyIGZyb20gdGhlIHdvcmxkIG9mIHlvdSBhbmQgSQpXaGVyZSBvY2VhbnMgYmxlZWQgaW50byB0aGUgc2t5CiovCnZlY3RvcjxpbnQ+IHNoOwp2ZWN0b3I8cGlpID4gdml2YTsKaW50IHRyZWVbMypNQVhdOwptYXA8aW50LGludD4gaW5kLGNudHI7CnZvaWQgdXBkYXRlKGludCBuLGludCBsLGludCByLGludCBpLGludCB2KQp7CiAgICBpZihpPnIpCiAgICAgICAgcmV0dXJuIDsKICAgIGlmKGk8bCkKICAgICAgICByZXR1cm4gOwogICAgaWYobD09ciYmbD09aSkKICAgIHsKICAgICAgICB0cmVlW25dPXY7CiAgICAgICAgcmV0dXJuIDsKICAgIH0KICAgIGludCBtaWQ9bCtyOwogICAgbWlkLz0yOwogICAgdXBkYXRlKDIqbixsLG1pZCxpLHYpOwogICAgdXBkYXRlKDIqbisxLG1pZCsxLHIsaSx2KTsKICAgIHRyZWVbbl09dHJlZVsyKm5dK3RyZWVbMipuKzFdOwogICAgcmV0dXJuIDsKCn0KaW50IHF1ZXJ5KGludCBuLGludCBsLGludCByLGludCBpLGludCBqKQp7Ci8vICAgIGNvdXQ8PGk8PCcgJzw8ajw8ZW5kbDsKICAgIGlmKGk+cnx8ajxsKQogICAgICAgIHJldHVybiAwOwogICAgaWYoaTw9bCYmaj49cikKICAgICAgICByZXR1cm4gdHJlZVtuXTsKICAgIGludCBtaWQ9bCtyOwogICAgbWlkLz0yOwogICAgcmV0dXJuIHF1ZXJ5KDIqbixsLG1pZCxpLGopK3F1ZXJ5KDIqbisxLG1pZCsxLHIsaSxqKTsKfQppbnQgcXVlcnlfMihpbnQgbixpbnQgbCxpbnQgcixpbnQgdmFsKQp7Ci8vICAgIGNvdXQ8PGw8PCcgJzw8cjw8JyAnPDx2YWw8PGVuZGw7CiAgICBpZih0cmVlW25dPHZhbCkKICAgICAgICByZXR1cm4gLTE7CiAgICBpZihsPT1yKQogICAgewogICAgICAgIHJldHVybiBsOwogICAgfQogICAgaW50IG1pZD1sK3I7CiAgICBtaWQvPTI7CiAgICBpZih0cmVlWzIqbl0+PXZhbCkKICAgICAgICByZXR1cm4gcXVlcnlfMigyKm4sbCxtaWQsdmFsKTsKICAgIGVsc2UKICAgICAgICByZXR1cm4gcXVlcnlfMigyKm4rMSxtaWQrMSxyLHZhbC10cmVlWzIqbl0pOwp9CmludCBtYWluKCkKewoJaW50IGksaixrLG4sbSxwLHEsdCx4LHk7CgljaGFyIGNoOwoJY2luPj5uOwogICAgZm9yIChpPTA7aTxuO2krKykKICAgIHsKICAgICAgICBjaW4+PmNoPj54OwogICAgICAgIHZpdmEucGIobXAoY2gseCkpOwogICAgICAgICAgICBzaC5wYih4KTsKICAgIH0KICAgIHVuaXF1ZShzaC5iZWdpbigpLHNoLmVuZCgpKTsKICAgIHNvcnQoc2guYmVnaW4oKSxzaC5lbmQoKSk7CiAgICBmb3IgKGk9MDtpPHNoLnNpemUoKTtpKyspCiAgICB7CiAgICAgICAgaW5kW3NoW2ldXT1pOwogICAgfQogICAgZm9yIChpPTA7aTxuO2krKykKICAgIHsKICAgICAgICBjaD12aXZhW2ldLmZpcnN0OwogICAgICAgIHg9dml2YVtpXS5zZWNvbmQ7CiAgICAgICAgaWYoY2g9PSdJJykKICAgICAgICB7Ci8vICAgICAgICAgICAgY291dDw8IklOU0VSVCI8PGVuZGw7Ci8vICAgICAgICAgICAgQ0hFQ0soeCkKLy8gICAgICAgICAgICBDSEVDSyhpbmRbeF0pOwogICAgICAgICAgICBpZighY250clt4XSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdXBkYXRlKDEsMCxuLGluZFt4XSwxKTsKICAgICAgICAgICAgICAgIGNudHJbeF0rKzsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBlbHNlIGlmKGNoPT0nRCcpCiAgICAgICAgewogICAgICAgICAgICBpZihjbnRyW3hdKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB1cGRhdGUoMSwwLG4saW5kW3hdLDApOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYoY2g9PSdDJykKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQ8PHF1ZXJ5KDEsMCxuLDAsaW5kW3hdLTEpPDxlbmRsOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKGNoPT0nSycpCiAgICAgICAgewogICAgICAgICAgICBrPXF1ZXJ5XzIoMSwwLG4seCk7CiAgICAgICAgICAgIGlmKH5rKQogICAgICAgICAgICBjb3V0PDxzaFtrXTw8ZW5kbDsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgY291dDw8ImludmFsaWQiPDxlbmRsOwogICAgICAgIH0KICAgIH0KCXJldHVybiAwOwp9Cg==