#include<bits/stdc++.h>
#define mp make_pair
#define N 100001
using namespace std;
int a[N],n; pair<int,int> s[5*N];
inline int scan(){
char c = getchar_unlocked();
int x = 0;
while(c<'0'||c>'9'){
c=getchar_unlocked();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+c-'0';
c=getchar_unlocked();
}
return x;
}
void make(int l, int r, int node){
if(l==r) s[node]=mp(a[l],l);
else{
int mid=l+r;
mid/=2;
make(l,mid,2*node);
make(mid+1,r,1+ 2*node);
s[node]=max(s[2*node], s[1+ 2*node]);
// cout<<l<<" "<<r<<" "<<s[node].first<<" "<<s[node].second<<endl;
}
}
void update(int l,int r,int node,int pos,int val){
if(l==r){
s[node]=mp(val,pos);
}
else{
int mid=(l+r)>>1;
int lc=node<<1;
int rc=lc|1;
if(mid>=pos){
update(l,mid,lc,pos,val);
}
else{
update(mid+1,r,rc,pos,val);
}
s[node]=max(s[lc],s[rc]);
}
}
pair<int,int> query(int start, int end, int node, int l, int r){
if(l<=start && end<=r) return s[node];
else if(l>end || r<start) return mp(-1,0);
int mid=start+end;
mid/=2;
return max(query(start,mid,2*node,l,r),query(mid+1,end,1+ 2*node,l,r));
}
int main(){
n=scan();
for(int i=1; i<=n; i++) a[i]=scan();
int q;
q=scan();
make(1,n,1);
//cout<<query(1,n,1,1,4).first;
while(q--){
char k;
cin>>k;
int l,r; l=scan(); r=scan();
if(k=='Q'){
int max_ind=query(1,n,1,l,r).second;
int max_val=a[max_ind];
int val=max_val;
//cout<<max_val<<endl;
update(1,n,1,max_ind,-1);
int max2_ind=query(1,n,1,l,r).second;
int max2_val=a[max2_ind];
//cout<<max2_val<<endl;
update(1,n,1,max_ind,max_val);
cout<<max_val+max2_val<<endl;
//cout<<endl<<endl;
}
else{
update(1,n,1,l,r);
a[l]=r;
}
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBOIDEwMDAwMQp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgYVtOXSxuOyBwYWlyPGludCxpbnQ+IHNbNSpOXTsKaW5saW5lIGludCBzY2FuKCl7CiAgICBjaGFyIGMgPSBnZXRjaGFyX3VubG9ja2VkKCk7CiAgICBpbnQgeCA9IDA7CiAgICB3aGlsZShjPCcwJ3x8Yz4nOScpewogICAgICAgIGM9Z2V0Y2hhcl91bmxvY2tlZCgpOwogICAgfQogICAgd2hpbGUoYz49JzAnJiZjPD0nOScpewogICAgICAgIHg9KHg8PDEpKyh4PDwzKStjLScwJzsKICAgICAgICBjPWdldGNoYXJfdW5sb2NrZWQoKTsKICAgIH0KICAgIHJldHVybiB4Owp9CnZvaWQgbWFrZShpbnQgbCwgaW50IHIsIGludCBub2RlKXsKCWlmKGw9PXIpIHNbbm9kZV09bXAoYVtsXSxsKTsKCWVsc2V7CgkJaW50IG1pZD1sK3I7CgkJbWlkLz0yOwoJCW1ha2UobCxtaWQsMipub2RlKTsKCQltYWtlKG1pZCsxLHIsMSsgMipub2RlKTsKCQlzW25vZGVdPW1heChzWzIqbm9kZV0sIHNbMSsgMipub2RlXSk7CiAgICAgIC8vICBjb3V0PDxsPDwiICI8PHI8PCIgIjw8c1tub2RlXS5maXJzdDw8IiAiPDxzW25vZGVdLnNlY29uZDw8ZW5kbDsKCX0KfQp2b2lkIHVwZGF0ZShpbnQgbCxpbnQgcixpbnQgbm9kZSxpbnQgcG9zLGludCB2YWwpewogICAgaWYobD09cil7CiAgICAgICAgc1tub2RlXT1tcCh2YWwscG9zKTsKICAgIH0KICAgIGVsc2V7CiAgICAgICAgaW50IG1pZD0obCtyKT4+MTsKICAgICAgICBpbnQgbGM9bm9kZTw8MTsKICAgICAgICBpbnQgcmM9bGN8MTsKICAgICAgICBpZihtaWQ+PXBvcyl7CiAgICAgICAgICAgIHVwZGF0ZShsLG1pZCxsYyxwb3MsdmFsKTsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgdXBkYXRlKG1pZCsxLHIscmMscG9zLHZhbCk7CiAgICAgICAgfQogICAgICAgIHNbbm9kZV09bWF4KHNbbGNdLHNbcmNdKTsKICAgIH0KfQpwYWlyPGludCxpbnQ+IHF1ZXJ5KGludCBzdGFydCwgaW50IGVuZCwgaW50IG5vZGUsIGludCBsLCBpbnQgcil7CglpZihsPD1zdGFydCAmJiBlbmQ8PXIpIHJldHVybiBzW25vZGVdOwoJZWxzZSBpZihsPmVuZCB8fCByPHN0YXJ0KSByZXR1cm4gbXAoLTEsMCk7CglpbnQgbWlkPXN0YXJ0K2VuZDsKCW1pZC89MjsKCXJldHVybiBtYXgocXVlcnkoc3RhcnQsbWlkLDIqbm9kZSxsLHIpLHF1ZXJ5KG1pZCsxLGVuZCwxKyAyKm5vZGUsbCxyKSk7Cn0KaW50IG1haW4oKXsKCW49c2NhbigpOwoJZm9yKGludCBpPTE7IGk8PW47IGkrKykgYVtpXT1zY2FuKCk7CglpbnQgcTsKCXE9c2NhbigpOwoJbWFrZSgxLG4sMSk7CiAgICAvL2NvdXQ8PHF1ZXJ5KDEsbiwxLDEsNCkuZmlyc3Q7Cgl3aGlsZShxLS0pewoJCWNoYXIgazsKCQljaW4+Pms7CgkJaW50IGwscjsgbD1zY2FuKCk7IHI9c2NhbigpOwoJCWlmKGs9PSdRJyl7CgkJCWludCBtYXhfaW5kPXF1ZXJ5KDEsbiwxLGwscikuc2Vjb25kOwoJCQlpbnQgbWF4X3ZhbD1hW21heF9pbmRdOwoJCQlpbnQgdmFsPW1heF92YWw7CiAgICAgICAgICAgIC8vY291dDw8bWF4X3ZhbDw8ZW5kbDsKCQkJdXBkYXRlKDEsbiwxLG1heF9pbmQsLTEpOwoJCQlpbnQgbWF4Ml9pbmQ9cXVlcnkoMSxuLDEsbCxyKS5zZWNvbmQ7CgkJCWludCBtYXgyX3ZhbD1hW21heDJfaW5kXTsKICAgICAgICAgICAgLy9jb3V0PDxtYXgyX3ZhbDw8ZW5kbDsKCQkJdXBkYXRlKDEsbiwxLG1heF9pbmQsbWF4X3ZhbCk7CgkJCWNvdXQ8PG1heF92YWwrbWF4Ml92YWw8PGVuZGw7CiAgICAgICAgICAgIC8vY291dDw8ZW5kbDw8ZW5kbDsKCQl9CgkJZWxzZXsKCQkJdXBkYXRlKDEsbiwxLGwscik7CgkJCWFbbF09cjsKCQl9IAoJfQp9