#include<bits/stdc++.h>
using namespace std;
#define mx 100009
#define ll long long int
ll arr[mx];
//ll tree[mx*4];
//ll state=0;
struct nd{
ll high;
ll sum;
};
nd tree[mx*4];
ll ans=-1;
ll res;
void init(ll node,ll l,ll r){
if(l==r){
tree[node].high=arr[l]; //cout<<"lf node:"<<node<<" val:"<<tree[node].high<<endl;
tree[node].sum=arr[l];
return;
}
ll Left=node*2;
ll Right=node*2+1;
ll mid=(l+r)/2;
init(Left,l,mid);
init(Right,mid+1,r);
tree[node].high=max(tree[Left].high,tree[Right].high);
ll hh=-1;
hh=max(hh,tree[Left].high+tree[Right].high);
hh=max(hh,tree[Left].sum);
hh=max(hh,tree[Right].sum);
tree[node].sum=hh; //cout<<"node:"<<node<<" val:"<<tree[node].sum<<" high:"<<tree[node].high<<endl;
}
ll query(ll node,ll l,ll r,ll i,ll j){
if(l>j || r<i){
return 0;
}
if(l>=i && r<=j){//cout<<"node:"<<node<<" val:"<<tree[node].sum<<endl; cout<<"l:"<<l<<" r:"<<r<<endl;
if(tree[node].sum>res){
res=tree[node].sum;
}
return tree[node].high;
}
ll Left=node*2;
ll Right=node*2+1;
ll mid=(l+r)/2;
ll p1=query(Left,l,mid,i,j);
ll p2=query(Right,mid+1,r,i,j);
if(p1+p2>res){ //cout<<p1<<"+"<<p2<<endl;
res=p1+p2;
}
return max(p1,p2);
}
void update(ll node,ll l,ll r,ll pos,ll val){
if(l>pos || r<pos){
return;
}
if(l==r){
tree[node].high=val;
tree[node].sum=val;
return;
}
ll Left=node*2;
ll Right=node*2+1;
ll mid=(l+r)/2;
update(Left,l,mid,pos,val);
update(Right,mid+1,r,pos,val);
tree[node].high=max(tree[Left].high,tree[Right].high);
tree[node].sum=max(tree[node].sum,tree[Left].high+tree[Right].high);
}
int main(){
ll n,i,j;
while(scanf("%lld",&n)==1){
for(i=1;i<=n;i++){
scanf("%lld",&arr[i]);
}
init(1,1,n);
char ch;
ll q;
scanf("%lld",&q);
getchar();
for(i=1;i<=q;i++){
scanf("%c",&ch);
if(ch=='Q'){
ll x,y; //cout<<"Q pressed"<<endl;
scanf("%lld %lld",&x,&y);
query(1,1,n,x,y);
printf("%lld\n",res);
res=-1;
//state=0;
}
else{
ll x,y;
scanf("%lld %lld",&x,&y);
update(1,1,n,x,y);
}
getchar();
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBteCAxMDAwMDkKI2RlZmluZSBsbCBsb25nIGxvbmcgaW50CmxsIGFycltteF07Ci8vbGwgdHJlZVtteCo0XTsKLy9sbCBzdGF0ZT0wOwpzdHJ1Y3QgbmR7CiAgICBsbCBoaWdoOwogICAgbGwgc3VtOwp9OwpuZCB0cmVlW214KjRdOwpsbCBhbnM9LTE7CmxsIHJlczsKdm9pZCBpbml0KGxsIG5vZGUsbGwgbCxsbCByKXsKICAgIGlmKGw9PXIpewogICAgICAgIHRyZWVbbm9kZV0uaGlnaD1hcnJbbF07IC8vY291dDw8ImxmIG5vZGU6Ijw8bm9kZTw8IiB2YWw6Ijw8dHJlZVtub2RlXS5oaWdoPDxlbmRsOwogICAgICAgIHRyZWVbbm9kZV0uc3VtPWFycltsXTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBsbCBMZWZ0PW5vZGUqMjsKICAgIGxsIFJpZ2h0PW5vZGUqMisxOwogICAgbGwgbWlkPShsK3IpLzI7CiAgICBpbml0KExlZnQsbCxtaWQpOwogICAgaW5pdChSaWdodCxtaWQrMSxyKTsKICAgIHRyZWVbbm9kZV0uaGlnaD1tYXgodHJlZVtMZWZ0XS5oaWdoLHRyZWVbUmlnaHRdLmhpZ2gpOwogICAgbGwgaGg9LTE7CiAgICBoaD1tYXgoaGgsdHJlZVtMZWZ0XS5oaWdoK3RyZWVbUmlnaHRdLmhpZ2gpOwogICAgaGg9bWF4KGhoLHRyZWVbTGVmdF0uc3VtKTsKICAgIGhoPW1heChoaCx0cmVlW1JpZ2h0XS5zdW0pOwogICAgdHJlZVtub2RlXS5zdW09aGg7IC8vY291dDw8Im5vZGU6Ijw8bm9kZTw8IiB2YWw6Ijw8dHJlZVtub2RlXS5zdW08PCIgaGlnaDoiPDx0cmVlW25vZGVdLmhpZ2g8PGVuZGw7Cn0KCmxsIHF1ZXJ5KGxsIG5vZGUsbGwgbCxsbCByLGxsIGksbGwgail7CiAgICBpZihsPmogfHwgcjxpKXsKICAgICAgICByZXR1cm4gMDsKICAgIH0KICAgIGlmKGw+PWkgJiYgcjw9ail7Ly9jb3V0PDwibm9kZToiPDxub2RlPDwiIHZhbDoiPDx0cmVlW25vZGVdLnN1bTw8ZW5kbDsgIGNvdXQ8PCJsOiI8PGw8PCIgcjoiPDxyPDxlbmRsOwogICAgICAgIGlmKHRyZWVbbm9kZV0uc3VtPnJlcyl7CiAgICAgICAgICAgIHJlcz10cmVlW25vZGVdLnN1bTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHRyZWVbbm9kZV0uaGlnaDsKICAgIH0KICAgIGxsIExlZnQ9bm9kZSoyOwogICAgbGwgUmlnaHQ9bm9kZSoyKzE7CiAgICBsbCBtaWQ9KGwrcikvMjsKICAgIGxsIHAxPXF1ZXJ5KExlZnQsbCxtaWQsaSxqKTsKICAgIGxsIHAyPXF1ZXJ5KFJpZ2h0LG1pZCsxLHIsaSxqKTsKICAgIGlmKHAxK3AyPnJlcyl7IC8vY291dDw8cDE8PCIrIjw8cDI8PGVuZGw7CiAgICAgICAgcmVzPXAxK3AyOwogICAgfQogICAgcmV0dXJuIG1heChwMSxwMik7Cn0KCnZvaWQgdXBkYXRlKGxsIG5vZGUsbGwgbCxsbCByLGxsIHBvcyxsbCB2YWwpewogICAgaWYobD5wb3MgfHwgcjxwb3MpewogICAgICAgIHJldHVybjsKICAgIH0KICAgIGlmKGw9PXIpewogICAgICAgIHRyZWVbbm9kZV0uaGlnaD12YWw7CiAgICAgICAgdHJlZVtub2RlXS5zdW09dmFsOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGxsIExlZnQ9bm9kZSoyOwogICAgbGwgUmlnaHQ9bm9kZSoyKzE7CiAgICBsbCBtaWQ9KGwrcikvMjsKICAgIHVwZGF0ZShMZWZ0LGwsbWlkLHBvcyx2YWwpOwogICAgdXBkYXRlKFJpZ2h0LG1pZCsxLHIscG9zLHZhbCk7CiAgICB0cmVlW25vZGVdLmhpZ2g9bWF4KHRyZWVbTGVmdF0uaGlnaCx0cmVlW1JpZ2h0XS5oaWdoKTsKICAgIHRyZWVbbm9kZV0uc3VtPW1heCh0cmVlW25vZGVdLnN1bSx0cmVlW0xlZnRdLmhpZ2grdHJlZVtSaWdodF0uaGlnaCk7Cn0KCmludCBtYWluKCl7CiAgICBsbCBuLGksajsKICAgIHdoaWxlKHNjYW5mKCIlbGxkIiwmbik9PTEpewogICAgICAgIGZvcihpPTE7aTw9bjtpKyspewogICAgICAgICAgICBzY2FuZigiJWxsZCIsJmFycltpXSk7CiAgICAgICAgfQogICAgICAgIGluaXQoMSwxLG4pOwogICAgICAgIGNoYXIgY2g7CiAgICAgICAgbGwgcTsKICAgICAgICBzY2FuZigiJWxsZCIsJnEpOwogICAgICAgIGdldGNoYXIoKTsKICAgICAgICBmb3IoaT0xO2k8PXE7aSsrKXsKICAgICAgICAgICAgc2NhbmYoIiVjIiwmY2gpOwogICAgICAgICAgICBpZihjaD09J1EnKXsKICAgICAgICAgICAgICAgIGxsIHgseTsgLy9jb3V0PDwiUSBwcmVzc2VkIjw8ZW5kbDsKICAgICAgICAgICAgICAgIHNjYW5mKCIlbGxkICVsbGQiLCZ4LCZ5KTsKICAgICAgICAgICAgICAgIHF1ZXJ5KDEsMSxuLHgseSk7CiAgICAgICAgICAgICAgICBwcmludGYoIiVsbGRcbiIscmVzKTsKICAgICAgICAgICAgICAgIHJlcz0tMTsKICAgICAgICAgICAgICAgIC8vc3RhdGU9MDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgbGwgeCx5OwogICAgICAgICAgICAgICAgc2NhbmYoIiVsbGQgJWxsZCIsJngsJnkpOwogICAgICAgICAgICAgICAgdXBkYXRlKDEsMSxuLHgseSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZ2V0Y2hhcigpOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9