//Pranet Verma
#include <bits/stdc++.h>
using namespace std;
namespace Splay
{
typedef struct Node* pnode;
pnode null;
struct Node
{
int val,mx,sz;
pnode c[2],p;
};
// void display(pnode u)
// {
// if(u==null)
// return;
// display(u->c[0]);
// cout<<u->val<<" "<<endl;
// display(u->c[1]);
// }
bool getDir(pnode p,pnode x)
{
return p->c[1]==x;
}
void setLink(pnode x,pnode y,int d)
{
if(x!=null)
x->c[d]=y;
if(y!=null)
y->p=x;
}
void update(pnode u)
{
if(u==null)
return;
u->sz=1+u->c[0]->sz+u->c[1]->sz;
u->mx=max(u->val,max(u->c[0]->mx,u->c[1]->mx));
}
void rotate(pnode y,bool d)
{
pnode x=y->c[d],z=y->p;
setLink(y,x->c[d^1],d);
setLink(x,y,d^1);
setLink(z,x,getDir(z,y));
update(x);update(y);
}
void splay(pnode x)
{
while(x->p!=null)
{
pnode y=x->p,z=y->p;
int dy=getDir(y,x),dz=getDir(z,y);
if(z==null)
rotate(y,dy);
else if(dy==dz)
rotate(z,dz),rotate(y,dy);
else
rotate(y,dy),rotate(z,dz);
}
}
pnode get(pnode u,int key,int add)
{
while(1)
{
int rank=1+add+u->c[0]->sz;
if(rank==key)
{
splay(u);
return u;
}
else if(rank<key)
{
add=rank;
u=u->c[1];
}
else
u=u->c[0];
}
}
void split(pnode u,pnode &l,pnode &r,int key,int add)
{
if(key==add)
{
l=null;
r=u;
}
else
{
l=get(u,key,add);
r=l->c[1];
l->c[1]=r->p=null;
update(l);
}
}
void merge(pnode &u,pnode x,pnode y)
{
if(x==null)
u=y;
else if(y==null)
u=x;
else
{
u=get(x,x->sz,0);
setLink(u,y,1);
update(u);
}
}
const int MAXN=100005;
Node buff[MAXN],*ptr=buff;
pnode newNode()
{
return ++ptr;
}
}
using namespace Splay;
int main()
{
null= newNode();
null->val=null->mx=-1e9-9;
null->sz=0;
null->c[0]=null->c[1]=null->p=null;
int m;
scanf("%d\n",&m);
pnode root=null;
while(m--)
{
char ty;
int x,y;
scanf("%c %d %d\n",&ty,&x,&y);
if(ty=='A')
{
pnode a,b;
split(root,a,b,y-1,0);
root=newNode();
root->val=root->mx=x;
root->sz=1;
root->c[0]=a;
root->c[1]=b;
root->p=null;
// update(root);
a->p=b->p=root;
}
else if(ty=='Q')
{
pnode a,b,c;
split(root,a,b,x-1,0);
split(b,b,c,y,a->sz);
printf("%d\n",b->mx);
merge(b,b,c);
merge(root,a,b);
}
else
assert(0);
}
}
Ly9QcmFuZXQgVmVybWEKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cm5hbWVzcGFjZSBTcGxheQp7CiAgICB0eXBlZGVmIHN0cnVjdCBOb2RlKiBwbm9kZTsKICAgIHBub2RlIG51bGw7CiAgICBzdHJ1Y3QgTm9kZQogICAgewogICAgICAgIGludCB2YWwsbXgsc3o7CiAgICAgICAgcG5vZGUgY1syXSxwOwogICAgfTsKICAgIC8vIHZvaWQgZGlzcGxheShwbm9kZSB1KQogICAgLy8gewogICAgLy8gICAgIGlmKHU9PW51bGwpCiAgICAvLyAgICAgICAgIHJldHVybjsKICAgIC8vICAgICBkaXNwbGF5KHUtPmNbMF0pOwogICAgLy8gICAgIGNvdXQ8PHUtPnZhbDw8IiAiPDxlbmRsOwogICAgLy8gICAgIGRpc3BsYXkodS0+Y1sxXSk7ICAgICAgICAKICAgIC8vIH0KICAgIGJvb2wgZ2V0RGlyKHBub2RlIHAscG5vZGUgeCkKICAgIHsKICAgICAgICByZXR1cm4gcC0+Y1sxXT09eDsKICAgIH0KICAgIHZvaWQgc2V0TGluayhwbm9kZSB4LHBub2RlIHksaW50IGQpCiAgICB7CiAgICAgICAgaWYoeCE9bnVsbCkKICAgICAgICAgICAgeC0+Y1tkXT15OwogICAgICAgIGlmKHkhPW51bGwpCiAgICAgICAgICAgIHktPnA9eDsKICAgIH0KICAgIHZvaWQgdXBkYXRlKHBub2RlIHUpCiAgICB7CiAgICAgICAgaWYodT09bnVsbCkKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIHUtPnN6PTErdS0+Y1swXS0+c3ordS0+Y1sxXS0+c3o7CiAgICAgICAgdS0+bXg9bWF4KHUtPnZhbCxtYXgodS0+Y1swXS0+bXgsdS0+Y1sxXS0+bXgpKTsKICAgIH0KICAgIHZvaWQgcm90YXRlKHBub2RlIHksYm9vbCBkKQogICAgewogICAgICAgIHBub2RlIHg9eS0+Y1tkXSx6PXktPnA7CiAgICAgICAgc2V0TGluayh5LHgtPmNbZF4xXSxkKTsKICAgICAgICBzZXRMaW5rKHgseSxkXjEpOwogICAgICAgIHNldExpbmsoeix4LGdldERpcih6LHkpKTsKICAgICAgICB1cGRhdGUoeCk7dXBkYXRlKHkpOwogICAgfQogICAgdm9pZCBzcGxheShwbm9kZSB4KQogICAgewogICAgICAgIHdoaWxlKHgtPnAhPW51bGwpCiAgICAgICAgewogICAgICAgICAgICBwbm9kZSB5PXgtPnAsej15LT5wOwogICAgICAgICAgICBpbnQgZHk9Z2V0RGlyKHkseCksZHo9Z2V0RGlyKHoseSk7CiAgICAgICAgICAgIGlmKHo9PW51bGwpCiAgICAgICAgICAgICAgICByb3RhdGUoeSxkeSk7CiAgICAgICAgICAgIGVsc2UgaWYoZHk9PWR6KQogICAgICAgICAgICAgICAgcm90YXRlKHosZHopLHJvdGF0ZSh5LGR5KTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgcm90YXRlKHksZHkpLHJvdGF0ZSh6LGR6KTsKICAgICAgICB9CiAgICB9CiAgICBwbm9kZSBnZXQocG5vZGUgdSxpbnQga2V5LGludCBhZGQpCiAgICB7CiAgICAgICAgd2hpbGUoMSkKICAgICAgICB7CiAgICAgICAgICAgIGludCByYW5rPTErYWRkK3UtPmNbMF0tPnN6OwogICAgICAgICAgICBpZihyYW5rPT1rZXkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHNwbGF5KHUpOwogICAgICAgICAgICAgICAgcmV0dXJuIHU7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSBpZihyYW5rPGtleSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgYWRkPXJhbms7CiAgICAgICAgICAgICAgICB1PXUtPmNbMV07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgdT11LT5jWzBdOwogICAgICAgIH0KICAgIH0KICAgIHZvaWQgc3BsaXQocG5vZGUgdSxwbm9kZSAmbCxwbm9kZSAmcixpbnQga2V5LGludCBhZGQpCiAgICB7CiAgICAgICAgaWYoa2V5PT1hZGQpCiAgICAgICAgewogICAgICAgICAgICBsPW51bGw7CiAgICAgICAgICAgIHI9dTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgbD1nZXQodSxrZXksYWRkKTsKICAgICAgICAgICAgcj1sLT5jWzFdOwogICAgICAgICAgICBsLT5jWzFdPXItPnA9bnVsbDsKICAgICAgICAgICAgdXBkYXRlKGwpOwogICAgICAgIH0KICAgIH0KICAgIHZvaWQgbWVyZ2UocG5vZGUgJnUscG5vZGUgeCxwbm9kZSB5KQogICAgewogICAgICAgIGlmKHg9PW51bGwpCiAgICAgICAgICAgIHU9eTsKICAgICAgICBlbHNlIGlmKHk9PW51bGwpCiAgICAgICAgICAgIHU9eDsKICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICB1PWdldCh4LHgtPnN6LDApOwogICAgICAgICAgICBzZXRMaW5rKHUseSwxKTsKICAgICAgICAgICAgdXBkYXRlKHUpOwogICAgICAgIH0KICAgIH0KICAgIGNvbnN0IGludCBNQVhOPTEwMDAwNTsKICAgIE5vZGUgYnVmZltNQVhOXSwqcHRyPWJ1ZmY7CiAgICBwbm9kZSBuZXdOb2RlKCkKICAgIHsKICAgICAgICByZXR1cm4gKytwdHI7CiAgICB9Cn0gICAKdXNpbmcgbmFtZXNwYWNlIFNwbGF5OwppbnQgbWFpbigpCnsKICAgIG51bGw9IG5ld05vZGUoKTsKICAgIG51bGwtPnZhbD1udWxsLT5teD0tMWU5LTk7CiAgICBudWxsLT5zej0wOwogICAgbnVsbC0+Y1swXT1udWxsLT5jWzFdPW51bGwtPnA9bnVsbDsKICAgIGludCBtOwogICAgc2NhbmYoIiVkXG4iLCZtKTsKICAgIHBub2RlIHJvb3Q9bnVsbDsKICAgIHdoaWxlKG0tLSkKICAgIHsKICAgICAgICBjaGFyIHR5OwogICAgICAgIGludCB4LHk7CiAgICAgICAgc2NhbmYoIiVjICVkICVkXG4iLCZ0eSwmeCwmeSk7CiAgICAgICAgaWYodHk9PSdBJykKICAgICAgICB7CiAgICAgICAgICAgIHBub2RlIGEsYjsKICAgICAgICAgICAgc3BsaXQocm9vdCxhLGIseS0xLDApOwogICAgICAgICAgICByb290PW5ld05vZGUoKTsKICAgICAgICAgICAgcm9vdC0+dmFsPXJvb3QtPm14PXg7CiAgICAgICAgICAgIHJvb3QtPnN6PTE7CiAgICAgICAgICAgIHJvb3QtPmNbMF09YTsKICAgICAgICAgICAgcm9vdC0+Y1sxXT1iOwogICAgICAgICAgICByb290LT5wPW51bGw7CiAgICAgICAgICAgIC8vIHVwZGF0ZShyb290KTsKICAgICAgICAgICAgYS0+cD1iLT5wPXJvb3Q7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYodHk9PSdRJykKICAgICAgICB7CiAgICAgICAgICAgIHBub2RlIGEsYixjOwogICAgICAgICAgICBzcGxpdChyb290LGEsYix4LTEsMCk7CiAgICAgICAgICAgIHNwbGl0KGIsYixjLHksYS0+c3opOwogICAgICAgICAgICBwcmludGYoIiVkXG4iLGItPm14KTsKICAgICAgICAgICAgbWVyZ2UoYixiLGMpOwogICAgICAgICAgICBtZXJnZShyb290LGEsYik7CiAgICAgICAgfSAgIAogICAgICAgIGVsc2UKICAgICAgICAgICAgYXNzZXJ0KDApOwogICAgfQp9