## Editorial for Giá trị lớn nhất 3

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

uses math;
const fi='';
maxn=100010;
oo=2000000000;
var b:array[1..maxn,0..2] of longint;
a,g,h:array[0..maxn*5] of longint;
c,pos,re:array[0..maxn] of longint;
n,m:longint;

procedure init(node,l,r:longint);
var mid:longint;
begin
if l=r then
begin
h[node]:=l; pos[l]:=node;
a[node]:=c[l];
end
else
begin
mid:=(l+r) shr 1;
init(node shl 1,l,mid);
init(node shl 1+1,mid+1,r);
h[node]:=h[node shl 1];
a[node]:=max(a[node shl 1],a[node shl 1+1]);
end;
end;

procedure rf;
var i:longint; c:char;
begin
n:=0;
for i:=1 to m do
begin
if c='Q' then b[i,0]:=1
else inc(n);
end;
init(1,1,n);
end;

function find(node,l,r,val:longint):longint;
var mid:longint;
begin
if l=r then find:=l
else
begin
mid:=(l+r) shr 1;
val:=val+g[node];
if h[node shl 1+1]<=val then
find:=find(node shl 1+1,mid+1,r,val)
else find:=find(node shl 1,l,mid,val);
end;
end;

procedure incr(node,l,r,x,y:longint);
var mid:longint;
begin
if (l=x) and (r=y) then
begin
g[node]:=g[node]+1;
h[node]:=h[node]-1;
end
else
begin
mid:=(l+r) shr 1;
if x<=mid then incr(node shl 1,l,mid,x,min(y,mid));
if y>mid then incr(node shl 1+1,mid+1,r,max(x,mid+1),y);
h[node]:=min(h[node shl 1],h[node shl 1+1])-g[node];
end;
end;

procedure update(x:longint);
begin
while x>1 do
begin
x:=x shr 1;
h[x]:=min(h[x shl 1],h[x shl 1+1])-g[x];
a[x]:=max(a[x shl 1],a[x shl 1+1]);
end;
end;

procedure get(node,l,r,x,y:longint;var re:longint);
var mid,t,u:longint;
begin
if (l=x) and (r=y) then re:=a[node]
else
begin
mid:=(l+r) shr 1;
t:=-oo; u:=-oo;
if x<=mid then get(node shl 1,l,mid,x,min(y,mid),t);
if mid<y then get(node shl 1+1,mid+1,r,max(x,mid+1),y,u);
re:=max(t,u);
end;
end;

procedure pr;
var i,x,y,dem:longint;
begin
for i:=m downto 1 do
if b[i,0]=0 then
begin
x:=find(1,1,n,b[i,2]);
if x<n then incr(1,1,n,x+1,n);
c[x]:=b[i,1];
h[pos[x]]:=oo;
update(pos[x]);
end;
fillchar(g,sizeof(g),0);
init(1,1,n);
dem:=0;
for i:=m downto 1 do
if b[i,0]=0 then
begin
x:=find(1,1,n,b[i,2]);
if x<n then incr(1,1,n,x+1,n);
h[pos[x]]:=oo; a[pos[x]]:=-oo;
update(pos[x]);
end
else
begin
dem:=dem+1;
x:=find(1,1,n,b[i,1]);
y:=find(1,1,n,b[i,2]);
get(1,1,n,x,y,re[dem]);
end;
while dem>0 do
begin
writeln(re[dem]);
dec(dem);
end;
end;

begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.


#### Code mẫu của happyboy99x

#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;

const int N = 1e5+7;
int bit1[2*N], m, n, st[4*N], bit2[2*N];
struct query {
char type;
int x, y;
scanf(" %c%d%d", &type, &x, &y);
}
} q[N];

void updateBIT(int * bit, int i, int v) {
for(; i <= n; i += i & -i)
bit[i] += v;
}

int findBIT(int * bit, int v) {
int res = n;
for(int mask = n >> 1; mask != 0 && res >= 1; mask >>= 1) {
int t = res - mask;
if(v <= bit[t]) res = t;
else v -= bit[t];
}
return res;
}

int sumBIT(int * bit, int i) {
int res = 0;
for(; i != 0; i -= i & -i)
res += bit[i];
return res;
}

void updateST(int k, int l, int r, int u, int v) {
if(u < l || u > r || l > r) return;
if(l == r) st[k] = max(st[k], v);
else {
updateST(2*k, l, (l+r)/2, u, v);
updateST(2*k+1, (l+r)/2+1, r, u, v);
st[k] = max(st[2*k], st[2*k+1]);
}
}

int getST(int k, int l, int r, int u, int v) {
if(v < l || r < u || l > r) return st[0];
if(u <= l && r <= v) return st[k];
return max(getST(2*k, l, (l+r)/2, u, v), getST(2*k+1, (l+r)/2+1, r, u, v));
}

void enter() {
scanf("%d", &m);
for(int i = 1; i <= m; ++i) {
if(q[i].type == 'A') ++n;
}
}

void standardizate() {
while(n & (n-1)) n -= n & -n; n <<= 1;
for(int i = 1; i <= n; ++i) updateBIT(bit2, i, 1);
for(int i = m; i >= 1; --i)
if(q[i].type == 'A') {
int backup = q[i].y;
q[i].y = findBIT(bit2, q[i].y);
updateBIT(bit1, backup, 1);
updateBIT(bit2, q[i].y, -1);
} else {
q[i].x = findBIT(bit2, q[i].x);
q[i].y = findBIT(bit2, q[i].y);
}
}

void solve() {
memset(st, 0xc1, sizeof st);
for(int i = 1; i <= m; ++i) {
if(q[i].type == 'A')
updateST(1, 1, n, q[i].y, q[i].x);
else
printf("%d\n", getST(1, 1, n, q[i].x, q[i].y));
}
}

int main() {
enter();
standardizate();
solve();
return 0;
}


#### Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

int INP,AM;
#define BUFSIZE (1<<10)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
if(!*inp) { \
inp=BUF; \
} \
INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
AM=0;\
GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
if (INP=='-') {AM=1;GETCHAR(INP);} \
j=INP-'0'; GETCHAR(INP); \
while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
if (AM) j=-j;\
}
//End of buffer reading

const double PI = acos(-1.0);
const int oo = 1000111000;

struct Node {
Node *ch[2];
int p;
int size;
int key, maxVal;

Node(int newKey) {
ch[0] = ch[1] = NULL;
size = 1;
p = rand();
key = maxVal = newKey;
}
} *root;

void print2(Node *p) {
if (!p) return ;
print2(p->ch[0]);
printf("%d ", p->key);
print2(p->ch[1]);
}

void print(Node *p) {
if (!p) { puts("Bst (0): ."); return ; }
printf("Bst (%d): ", p->size);
print2(p);
puts(".");
}

void update(Node *p) {
if (p == NULL) return ;
p->size = 1;
p->maxVal = p->key;
REP(b,2) if (p->ch[b]) {
p->size += p->ch[b]->size;
p->maxVal = max(p->maxVal, p->ch[b]->maxVal);
}
}

Node *rotate(Node *t, int b) {
Node *s = t->ch[1-b]; t->ch[1-b] = s->ch[b]; s->ch[b] = t;
update(t); update(s);
return s;
}

inline int getSize(Node *p) {
return p ? p->size : 0;
}

Node *get(Node *p, int k) {
if (!p) return p;
if (k <= getSize(p->ch[0])) return get(p->ch[0], k);
k -= getSize(p->ch[0])+1;
if (!k) return p;
return get(p->ch[1], k);
}

Node *insert(Node *p, int k, int x) {
if (!p) return new Node(x);
int b = !(k <= getSize(p->ch[0]) + 1);

if (!b) p->ch[0] = insert(p->ch[0], k, x);
else p->ch[1] = insert(p->ch[1], k - getSize(p->ch[0]) - 1, x);

if (p->p > p->ch[b]->p) p = rotate(p, 1-b);
update(p);
return p;
}

Node *erase(Node *p, int k) {
if (!p) return p;
if (k == getSize(p->ch[0]) + 1) {
if (!p->ch[0] && !p->ch[1]) return NULL;
else if (!p->ch[0]) p = rotate(p, 0);
else if (!p->ch[1]) p = rotate(p, 1);
else p = rotate(p, p->ch[0]->p < p->ch[1]->p);
p = erase(p, k);
}
else {
if (k <= getSize(p->ch[0])) p->ch[0] = erase(p->ch[0], k);
else p->ch[1] = erase(p->ch[1], k-getSize(p->ch[0])-1);
}
update(p);
return p;
}

int getMax(Node *p, int l, int r, int u, int v) {
if (!p || l > r) return -oo;
if (v < l || r < u) return -oo;
if (u <= l && r <= v) return p->maxVal;
int mid = l + getSize(p->ch[0]);
int res = -oo;
if (u <= mid && mid <= v) res = p->key;
return max(max(getMax(p->ch[0], l, mid-1, u, v), getMax(p->ch[1], mid+1, r, u, v)), res);
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
int q, x, y; scanf("%d\n", &q);
while (q--) {
char c = getchar();
if (c == 'A') {
scanf("%d %d\n", &x, &y);
root = insert(root, y, x);
}
else {
scanf("%d %d\n", &x, &y);
printf("%d\n", getMax(root, 1, root->size, x, y));
}
//        print(root);
}
return 0;
}


#### Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <utility>
#include <vector>
#define MAX_LEVEL 17
using namespace std;

int INF = (1 << 30) - 5,Q;

struct node
{
int level,value;
node* nextNode[MAX_LEVEL];
int width[MAX_LEVEL];
int maxValue[MAX_LEVEL];

node(int _L,int _V)
{
level = _L;  value = _V;
for (int i = 0; i <= level; i++)
{
width[i] = 1;  nextNode[i] = NULL;  maxValue[i] = value;
}
}
};

int randomLevel()
{
int L = 0;
while (rand() % 2 < 1 && L + 1 < MAX_LEVEL) L++;
return L;
}

struct skipList
{

void init()
{
head = new node(MAX_LEVEL - 1,-INF);
}

void insert(int pos,int value)
{
node* A = head;

int tmp = 0;
for (int i = head->level; i >= 0; i--)
{
while (tmp + A->width[i] < pos)
{
tmp += A->width[i];  A = A->nextNode[i];
}
}

node* B = new node(randomLevel(),value);
for (int i = 0; i <= B->level; i++)
{
}

for (int i = B->level + 1; i <= head->level; i++)
{
}

for (int i = 1; i <= B->level; i++)
{
node* C = link[i];
while (C != B)
{
link[i]->width[i] += C->width[i - 1];
C = C->nextNode[i - 1];
}
}

B->width[0] = 1;  B->maxValue[0] = value;
for (int i = 1; i <= B->level; i++)
{
B->width[i] = 0;  B->maxValue[i] = B->maxValue[i - 1];
node* C = B;
while (C != B->nextNode[i])
{
B->width[i] += C->width[i - 1];
B->maxValue[i] = max(B->maxValue[i],C->maxValue[i - 1]);
C = C->nextNode[i - 1];
}
}
}

int maximum(int x,int y)
{
node* A = head;
int tmp = 0;
for (int i = head->level; i >= 0; i--)
while (tmp + A->width[i] <= x)
{
tmp += A->width[i];  A = A->nextNode[i];
}

int ret = -INF;
int gap = y - x + 1,i = 0;
while (gap > 0)
{
while (i < A->level && A->width[i + 1] <= gap) i++;
while (A->width[i] > gap) i--;
ret = max(ret,A->maxValue[i]);
gap -= A->width[i];  A = A->nextNode[i];
}
return ret;
}
} S;

int main()
{
scanf("%d\n", &Q);
S.init();

while (Q--)
{
char arg;  int x,y;
while (1)
{
scanf("%c", &arg);
if (arg == 'Q' || arg == 'A') break;
}
scanf("%d %d\n", &x, &y);
if (arg == 'A') S.insert(y,x); else printf("%d\n", S.maximum(x,y));
}
}


#### Code mẫu của skyvn97

#include<cstdio>
const int INF=(int)2e9;
struct node {
int val,maxv,high,balance,nnode;
node *parent,*left,*right;
node(){}
void print(void) const {
printf("Node properties: %d|%d|%d|%d|%d\n",val,maxv,high,balance,nnode);
//      if (this->left==NULL) printf("Left null\n"); else printf("Left %d\n",this->left->val);
//      if (this->right==NULL) printf("Right null\n"); else printf("Right %d\n",this->right->val);
}
};
node *root;
int max(const int &x,const int &y) {
if (x>y) return (x); else return (y);
}
int max(int x,int y,int z) {
return (max(max(x,y),z));
}
void tree_init() {
root=NULL;
}
void treeview(node *a,int l) {
if (a==NULL) return;
int i;
for (i=1;i<=l;i=i+1) printf("\t");
printf("%d|%d|%d|%d|%d\n",a->val,a->maxv,a->high,a->balance,a->nnode);
//  system("Pause");
for (i=1;i<=l;i=i+1) printf("\t");
printf("Left\n");
treeview(a->left,l+1);
for (i=1;i<=l;i=i+1) printf("\t");
printf("Right\n");
treeview(a->right,l+1);
}
void create(node *&p,const int &x) {
if (p!=NULL) return;
p=new node();
p->val=x;
p->maxv=x;
p->high=1;
p->balance=0;
p->nnode=1;
p->parent=NULL;
p->left=NULL;
p->right=NULL;
}
void calculate(node *p) {
if (p==NULL) return;
//  printf("Before %d|%d|%d|%d|%d\n",p->val,p->maxv,p->high,p->balance,p->nnode);
int l,r;
if (p->left==NULL) l=0; else l=p->left->high;
if (p->right==NULL) r=0; else r=p->right->high;
p->high=max(l,r)+1;
p->balance=l-r;
if (p->left==NULL) l=0; else l=p->left->nnode;
if (p->right==NULL) r=0; else r=p->right->nnode;
p->nnode=l+r+1;
if (p->left==NULL) l=-INF; else l=p->left->maxv;
if (p->right==NULL) r=-INF; else r=p->right->maxv;
p->maxv=max(l,r,p->val);
//  printf("After %d|%d|%d|%d|%d\n",p->val,p->maxv,p->high,p->balance,p->nnode);
}
void link(node *a,node *b,int dir) {
if (a==NULL) {
root=b;
if (root!=NULL) root->parent=NULL;
return;
}
if (dir==1) a->left=b; else a->right=b;
if (b!=NULL) b->parent=a;
}
void left_rotation(node *a) {
//printf("Left rotate %d\n",a->val);
node *b,*c;
int dir=0;
c=a->parent;
if (c!=NULL) {
if (c->left==a) dir=1;
else dir=2;
}
b=a->right;
calculate(a);
calculate(b);
//  a->print();
}
void right_rotation(node *a) {
//printf("Right rotate %d\n",a->val);
node *b,*c;
c=a->parent;
int dir=0;
if (c!=NULL) {
if (c->left==a) dir=1;
else dir=2;
}
b=a->left;
calculate(a);
calculate(b);
}
void rebalance(node *a) {
node *c;
while (a!=NULL) {
calculate(a);
c=a->parent;
//printf("rebalancing %d\n",a->val);
if (a->balance==2) {
if (a->left->balance==-1) left_rotation(a->left);
right_rotation(a);
}
if (a->balance==-2) {
if (a->right->balance==1) right_rotation(a->right);
left_rotation(a);
}
a=c;
}
}
void insert(const int &i,const int &x) {
//  printf("insert %d %d\n",i,x);
node *p,*q;
int rem=0;
int nleft;
int dir=0;
p=root;
q=NULL;
while (p!=NULL) {
q=p;
if (p->left==NULL) nleft=0;
else nleft=p->left->nnode;
if (rem+nleft+1>=i) {
p=p->left;
dir=1;
}
else {
rem+=nleft+1;
p=p->right;
dir=2;
}
}
//  if (q==NULL) printf("insert to root %d\n",dir);
//  else printf("insert to %d %d\n",q->val,dir);
if (p==NULL) {
create(p,x);
if (root==NULL) root=p;
else {
//treeview(root);
rebalance(p);
}
}
}
int maxhigh(node *a,int l,int r,int u,int v) {
//  printf("Get max %d %d %d %d\n",l,r,u,v);
//  if (a!=NULL) a->print();
//  else printf("NULL\n");
if (l>v) return (-INF);
if (r<u) return (-INF);
if (l>r) return (-INF);
if (v<u) return (-INF);
if (a==NULL) return (-INF);
if (u<=l && r<=v) return (a->maxv);
int nleft;
if (a->left==NULL) nleft=0;
else nleft=a->left->nnode;
int left=maxhigh(a->left,l,l+nleft-1,u,v);
int right=maxhigh(a->right,l+nleft+1,r,u,v);
int mid;
if (u<=l+nleft && l+nleft<=v) mid=a->val;
else mid=-INF;
return (max(left,mid,right));
}
int n,q;
int maxhigh(const int &u,const int &v) {
//  printf("Answering from %d to %d\n",u,v);
return (maxhigh(root,1,n,u,v));
}
void process(void) {
n=0;
tree_init();
char c;
int i,x,y;
scanf("%d",&q);
for (i=1;i<=q;i=i+1) {
scanf(" %c",&c);
scanf("%d",&x);
scanf("%d",&y);
if (c=='A') {
//          printf("Insertion started\n");
insert(y,x);
//          treeview(root,0);
//          printf("\n");
n++;
//          printf("Insertion completed\n");
//          system("pause");
}
else printf("%d\n",maxhigh(x,y));
}
}
int main(void) {
#ifndef ONLINE_JUDGE
//freopen("tmp.txt","r",stdin);
#endif
process();
return 0;
}


#### Code mẫu của khuc_tuan

#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

const int BITMASK = 0xFFFFF;

template <class E> struct Treap {

struct Node {
Node *L, *R, *P;
E value;
int total;
int rank;
E maxvalue;
int c;

Node(E value) : value(value), total(1), c(0) {
this->rank = rand() & BITMASK;
L = R = P = NULL;
}
void updateTotal() {
total = 1 + (L == NULL ? 0 : L->total) + (R == NULL ? 0 : R->total);
maxvalue = value;
if(L != NULL) maxvalue = max(maxvalue, L->maxvalue);
if(R != NULL) maxvalue = max(maxvalue, R->maxvalue);
}
};

Node *root;
int count;

Treap() {
root = NULL;
count = 0;
}

void rotateLeft(Node *node) {
Node *a = node->R;
Node *fa = node->P;
node->R = a->L;
a->L = node;
if(node->R != NULL) node->R->P = node;
node->P = a;
a->P = fa;
if(fa == NULL) root = a;
else
if(fa->L == node) fa->L = a;
else fa->R = a;
node->updateTotal();
a->updateTotal();
}

void rotateRight(Node *node) {
Node *a = node->L;
Node *fa = node->P;
node->L = a->R;
a->R = node;
if(node->L != NULL) node->L->P = node;
node->P = a;
a->P = fa;
if(fa == NULL) root = a;
else
if(fa->L == node) fa->L = a;
else fa->R = a;
node->updateTotal();
a->updateTotal();
}

void pushdown(Node *n) {
while(n->L != NULL || n->R != NULL) {
Node *p = n->L;
if(p == NULL || (n->R != NULL && n->R->rank < p->rank)) p = n->R;
if(p->rank < n->rank) {
if(p == n->L) rotateRight(n);
else rotateLeft(n);
}
else break;
}
}

void pushup(Node *n) {
while(n->P != NULL) {
if(n->rank < n->P->rank) {
if(n == n->P->L) rotateRight(n->P);
else rotateLeft(n->P);
}
else break;
}
}

void add(E value) {
++count;
if(root == NULL) root = new Node(value);
else {
Node *p = root;
while(true) {
p->total++;
bool lessoreq = !(p->value < value);
if(lessoreq && p->L != NULL) p = p->L;
else if(!lessoreq && p->R != NULL) p = p->R;
else break;
}
bool lessoreq = !(p->value < value);
if(lessoreq) {
p->L = new Node(value);
p->L->P = p;
pushup(p->L);
}
else {
p->R = new Node(value);
p->R->P = p;
pushup(p->R);
}
}
}

Node* find(E value) {
Node *p = root;
while(p != NULL) {
bool less = value < p->value;
bool gr = p->value < value;
if(!less && !gr) return p;
else if(less) p = p->L;
else p = p->R;
}
return NULL;
}

bool contain(E value) {
return find(value) != NULL;
}

void remove(E value) {
Node *p = find(value);
if(p != NULL) {
--count;
p->rank = 1<<30;
pushdown(p);
Node *fa = p->P;
if(fa != NULL)
if(p == fa->L) fa->L = NULL;
else fa->R = NULL;
if(fa == NULL) root = NULL;
while(fa != NULL) {
fa->total--;
fa = fa->P;
}
}
}

Node* findK(int k) {
Node *p = root;
int onleft = 0;
while(true) {
int newonleft = onleft + (p->L == NULL ? 0 : p->L->total);
if(newonleft == k) return p;
else if(newonleft > k) p = p->L;
else {
onleft = newonleft + 1;
p = p->R;
}
}
}

int toIndex(Node *n) {
if(n == NULL) return count;
int id = 0;
if(n->L != NULL) id = n->L->total;
while(n != NULL) {
Node *p = n->P;
if(p != NULL && p->R == n) id += (p->L == NULL ? 0 : p->L->total) + 1;
n = p;
}
return id;
}

Node* upperBound(Node *root, E value) {
if(root == NULL) return NULL;
bool less = value < root->value;
if(less) {
Node *r = upperBound(root->L, value);
if(r != NULL) return r;
else return root;
}
else return upperBound(root->R, value);
}

Node* lowerBound(Node *root, E value) {
if(root == NULL) return NULL;
bool leoreq = !(root->value < value);
if(leoreq) {
Node *r = lowerBound(root->L, value);
if(r != NULL) return r;
else return root;
}
else return lowerBound(root->R, value);
}

pair<Treap,Treap> split(int m) { // first m elements -> 1 tree, remains -> 1 tree
Treap left, right;
if(m >= count) return make_pair(*this,Treap());
else if(m <= 0) return make_pair(Treap(),*this);
else {
Node *p = findK(m);
p->rank = -1<<30;
pushup(p);
left.root = p->L;
p->L->P = NULL;
p->L = NULL;
p->updateTotal();
right.root = p;
left.count = (left.root == NULL ? 0 : left.root->total);
right.count = (right.root == NULL ? 0 : right.root->total);
p->rank = rand() & BITMASK;
right.pushdown(p);
return make_pair(left, right);
}
}

Treap mergeWith(Treap tr) {
if(tr.root == NULL) return *this;
if(root == NULL) return tr;
Node *p = tr.findK(0);
p->rank = -1<<30;
tr.pushup(p);
p->L = root;
root->P = p;
p->updateTotal();
Treap res;
res.root = p;
res.count = p->total;
p->rank = rand() & BITMASK;
res.pushdown(p);
return res;
}
};

Treap<int> tr;
char buf[1000];
int n, sz;

int main() {
scanf("%d", &n);
gets(buf);
for(int i=0;i<n;++i) {
gets(buf);
int x, y;
sscanf(buf+1, "%d%d", &x, &y);
if(buf[0] == 'A') {
if(sz == 0) tr.add(x);
else {
Treap<int>::Node *p = tr.findK((y == sz + 1) ? (sz - 1) : (y - 1));
p->rank = 1<<30;
tr.pushdown(p);
Treap<int>::Node *nn = new Treap<int>::Node(x);
if(y == sz + 1) p -> R = nn, nn->P = p;
else p -> L = nn, nn -> P = p;
for(Treap<int>::Node *q=nn;q!=NULL;q=q->P) q->updateTotal();
p->rank = rand() & BITMASK;
tr.pushup(p);
tr.pushup(nn);
}
++sz;
}
else {
Treap<int>::Node *u = tr.findK(x - 1);
Treap<int>::Node *v = tr.findK(y - 1);
Treap<int>::Node *p, *fa;
for(p=u;p!=NULL;p=p->P) p->c++;
for(p=v;p!=NULL;p=p->P) p->c++;
int res = u->value;
if(u->c < 2 && u->R != NULL) res = max( res, u->R->maxvalue);
p = u;
while(p->c < 2) {
fa = p->P;
if(fa->L == p) {
res = max( res, fa->value);
if(fa->c < 2 && fa->R != NULL) res = max( res, fa->R->maxvalue);
}
p = fa;
}

res = max(res, v->value);
if(v->c < 2 && v->L != NULL) res = max( res, v->L->maxvalue);
p = v;
while(p->c < 2) {
fa = p->P;
if(fa->R == p) {
res = max( res, fa->value);
if(fa->c < 2 && fa->L != NULL) res = max( res, fa->L->maxvalue);
}
p = fa;
}

for(p=u;p!=NULL;p=p->P) p->c--;
for(p=v;p!=NULL;p=p->P) p->c--;

printf("%d\n", res);
}
}
return 0;
}