///MAXIMUM SUM
#include <bits/stdc++.h>
#define debug(x,y) cout<<"debug "<<x<<" "<<y<<endl;
using namespace std;
int n,len,max1,max2,pos1;
int arr[100002],acum[320],pos_max[320];
void find_max(int x){
int maxi=0;
for(int i=len*x;i<(x+1)*len;i++){
if(maxi<arr[i]){
maxi=arr[i];
pos_max[x]=i;
}
}
acum[x]=maxi;
return;
}
void update(int x,int value){
arr[x]=value;
find_max(x/len);
return;
}
int query(int l,int r){
int sum=0,in=(l-1)/len,fin=(r-1)/len;
if(r-l<len){
for(int i=l;i<=r;i++){
if(sum<arr[i]){
sum=arr[i];
pos1=i;
}
}
return sum;
}
for(int i=l;i<in*len;i++){
if(sum<arr[i]){
sum=arr[i];
pos1=i;
}
}
for(in;in<fin;in++){
if(sum<acum[in]){
sum=acum[in];
pos1=pos_max[in];
}
}
for(int i=len*fin;i<=r;i++){
if(sum<arr[i]){
sum=arr[i];
pos1=i;
}
}
return sum;
}
int main() {
cin>>n;
len=sqrt(n);
for(int i=0;i<n;i++) scanf("%d",&arr[i]);
for(int i=0;i<(n+len-1)/len;i++) find_max(i);
int q,x,y;
char c;
scanf("%d",&q);
int aux;
while(q--){
scanf(" %c %d%d",&c,&x,&y);
if(c=='U'){
update(x-1,y);
}
else{
max1=query(x-1,y-1);
update(pos1,0);
aux=pos1;
//debug(pos1,max1)
max2=query(x-1,y-1);
//debug(pos1,max2)
printf("%d\n",max1+max2);
update(aux,max1);
}
}
return 0;
}
Ly8vTUFYSU1VTSBTVU0KCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIGRlYnVnKHgseSkgY291dDw8ImRlYnVnICI8PHg8PCIgIjw8eTw8ZW5kbDsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBuLGxlbixtYXgxLG1heDIscG9zMTsKaW50IGFyclsxMDAwMDJdLGFjdW1bMzIwXSxwb3NfbWF4WzMyMF07Cgp2b2lkIGZpbmRfbWF4KGludCB4KXsKCWludCBtYXhpPTA7Cglmb3IoaW50IGk9bGVuKng7aTwoeCsxKSpsZW47aSsrKXsKCQlpZihtYXhpPGFycltpXSl7CgkJCW1heGk9YXJyW2ldOwoJCQlwb3NfbWF4W3hdPWk7CgkJfQoJfQoJYWN1bVt4XT1tYXhpOwoJcmV0dXJuOwp9Cgp2b2lkIHVwZGF0ZShpbnQgeCxpbnQgdmFsdWUpewoJYXJyW3hdPXZhbHVlOwoJZmluZF9tYXgoeC9sZW4pOwoJcmV0dXJuOwp9CgppbnQgcXVlcnkoaW50IGwsaW50IHIpewoJaW50IHN1bT0wLGluPShsLTEpL2xlbixmaW49KHItMSkvbGVuOwoJaWYoci1sPGxlbil7CgkJZm9yKGludCBpPWw7aTw9cjtpKyspewoJCQlpZihzdW08YXJyW2ldKXsKCQkJCXN1bT1hcnJbaV07CgkJCQlwb3MxPWk7CgkJCX0KCQl9CgkJcmV0dXJuIHN1bTsKCX0KCWZvcihpbnQgaT1sO2k8aW4qbGVuO2krKyl7CgkJaWYoc3VtPGFycltpXSl7CgkJCXN1bT1hcnJbaV07CgkJCXBvczE9aTsKCQl9Cgl9Cglmb3IoaW47aW48ZmluO2luKyspewoJCWlmKHN1bTxhY3VtW2luXSl7CgkJCXN1bT1hY3VtW2luXTsKCQkJcG9zMT1wb3NfbWF4W2luXTsKCQl9Cgl9Cglmb3IoaW50IGk9bGVuKmZpbjtpPD1yO2krKyl7CgkJaWYoc3VtPGFycltpXSl7CgkJCXN1bT1hcnJbaV07CgkJCXBvczE9aTsKCQl9Cgl9CglyZXR1cm4gc3VtOwp9CgppbnQgbWFpbigpIHsKCWNpbj4+bjsKCWxlbj1zcXJ0KG4pOwoJZm9yKGludCBpPTA7aTxuO2krKykgc2NhbmYoIiVkIiwmYXJyW2ldKTsKCWZvcihpbnQgaT0wO2k8KG4rbGVuLTEpL2xlbjtpKyspIGZpbmRfbWF4KGkpOwoJaW50IHEseCx5OwoJY2hhciBjOwoJc2NhbmYoIiVkIiwmcSk7CglpbnQgYXV4OwoJd2hpbGUocS0tKXsKCQlzY2FuZigiICVjICVkJWQiLCZjLCZ4LCZ5KTsKCQlpZihjPT0nVScpewoJCQl1cGRhdGUoeC0xLHkpOwoJCX0gCgkJZWxzZXsKCQkJbWF4MT1xdWVyeSh4LTEseS0xKTsKCQkJdXBkYXRlKHBvczEsMCk7CgkJCWF1eD1wb3MxOwoJCQkvL2RlYnVnKHBvczEsbWF4MSkKCQkJbWF4Mj1xdWVyeSh4LTEseS0xKTsKCQkJLy9kZWJ1Zyhwb3MxLG1heDIpCgkJCXByaW50ZigiJWRcbiIsbWF4MSttYXgyKTsKCQkJdXBkYXRlKGF1eCxtYXgxKTsKCQl9Cgl9CglyZXR1cm4gMDsKfQ==