#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define FOR(i,n) for(long i=0;i<n;i++)
#define FORE(i,a,b) for(long i=a;i<b;i++)
typedef long long ll;
#define N 100001
void initialise(long b,long e,long node);
long query(long b,long e,long i,long j,long node);
void update(long b,long e,long x,long node);
ll arr[N],mat[5*N+1]; //mat contains the array position of maximum value in the node
void initialise(long b,long e,long node)
{
if(b==e)
mat[node]=b;
else{
initialise(b,(b+e)/2,2*node);
initialise((b+e)/2+1,e,2*node+1);
if(arr[mat[2*node]]>=arr[mat[2*node+1]])
mat[node]=mat[2*node];
else
mat[node]=mat[2*node+1];
}
return;
}
long query(long b,long e,long i,long j,long node)
{
long p1,p2;
if(i>e || j<b)
return -1;
else{
if(i<=b && j>=e)
return mat[node];
p1=query(b,(b+e)/2,i,j,2*node);
p2=query((b+e)/2+1,e,i,j,2*node+1);
if(p1==-1)
return p2;
else if(p2==-1)
return p1;
else if(arr[p1]>=arr[p2])
return p1;//mat[node]=p1;
else
return p2;//mat[node]=p2;
}
}
void update(long b,long e,long x,long node)
{
if(x>e || x<b)
return;
// if(arr[mat[node]] < arr[x])
// mat[node]=x;
else if(b!=e){
if(arr[mat[node]] < arr[x])
mat[node]=x;
update(b,(b+e)/2,x,2*node);
update((b+e)/2+1,e,x,2*node+1);
//return;
}
//return;
}
int main()
{
long n,q,i,j,p1,p2,l,m,temp;
char ch;
scanf("%ld",&n);
FORE(i,1,n+1)
scanf("%lld",arr+i);
arr[0]=0;
scanf("%ld",&q);
FOR(i,5*N)
mat[i]=-1;
initialise(1,n,1);
while(q--)
{
cin>>ch>>i>>j;
if(ch=='U')
{
arr[i]=j;
update(1,n,i,1);
}
else if(ch=='Q')
{
if(i>j)
{
temp=i;
i=j;
j=temp;
}
p1=query(1,n,i,j,1);
if(p1==i)
{
p2=query(1,n,i+1,j,1);
}
else if(p1==j)
{
p2=query(1,n,i,j-1,1);
}
else{
l=query(1,n,i,p1-1,1);
m=query(1,n,p1+1,j,1);
if(arr[l]>=arr[m])
p2=l;
else
p2=m;
}
printf("%lld\n",arr[p1]+arr[p2]);
}
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxhbGdvcml0aG0+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBGT1IoaSxuKSBmb3IobG9uZyBpPTA7aTxuO2krKykKI2RlZmluZSBGT1JFKGksYSxiKSBmb3IobG9uZyBpPWE7aTxiO2krKykKdHlwZWRlZiBsb25nIGxvbmcgbGw7CiNkZWZpbmUgTiAxMDAwMDEKCnZvaWQgaW5pdGlhbGlzZShsb25nIGIsbG9uZyBlLGxvbmcgbm9kZSk7CmxvbmcgcXVlcnkobG9uZyBiLGxvbmcgZSxsb25nIGksbG9uZyBqLGxvbmcgbm9kZSk7CnZvaWQgdXBkYXRlKGxvbmcgYixsb25nIGUsbG9uZyB4LGxvbmcgbm9kZSk7CgpsbCBhcnJbTl0sbWF0WzUqTisxXTsgLy9tYXQgY29udGFpbnMgdGhlIGFycmF5IHBvc2l0aW9uIG9mIG1heGltdW0gdmFsdWUgaW4gdGhlIG5vZGUKCnZvaWQgaW5pdGlhbGlzZShsb25nIGIsbG9uZyBlLGxvbmcgbm9kZSkKewogICAgaWYoYj09ZSkKICAgICAgICBtYXRbbm9kZV09YjsKICAgIGVsc2V7CiAgICAgICAgaW5pdGlhbGlzZShiLChiK2UpLzIsMipub2RlKTsKICAgICAgICBpbml0aWFsaXNlKChiK2UpLzIrMSxlLDIqbm9kZSsxKTsKICAgICAgICBpZihhcnJbbWF0WzIqbm9kZV1dPj1hcnJbbWF0WzIqbm9kZSsxXV0pCiAgICAgICAgICAgIG1hdFtub2RlXT1tYXRbMipub2RlXTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIG1hdFtub2RlXT1tYXRbMipub2RlKzFdOwogICAgfQogICAgcmV0dXJuOwp9Cgpsb25nIHF1ZXJ5KGxvbmcgYixsb25nIGUsbG9uZyBpLGxvbmcgaixsb25nIG5vZGUpCnsKICAgIGxvbmcgcDEscDI7CiAgICBpZihpPmUgfHwgajxiKQogICAgICAgIHJldHVybiAtMTsKICAgIGVsc2V7CiAgICAgICAgaWYoaTw9YiAmJiBqPj1lKQogICAgICAgICAgICByZXR1cm4gbWF0W25vZGVdOwogICAgICAgIHAxPXF1ZXJ5KGIsKGIrZSkvMixpLGosMipub2RlKTsKICAgICAgICBwMj1xdWVyeSgoYitlKS8yKzEsZSxpLGosMipub2RlKzEpOwogICAgICAgIGlmKHAxPT0tMSkKICAgICAgICAgICAgcmV0dXJuIHAyOwogICAgICAgIGVsc2UgaWYocDI9PS0xKQogICAgICAgICAgICByZXR1cm4gcDE7CiAgICAgICAgZWxzZSBpZihhcnJbcDFdPj1hcnJbcDJdKQogICAgICAgICAgICByZXR1cm4gcDE7Ly9tYXRbbm9kZV09cDE7CiAgICAgICAgZWxzZQogICAgICAgICAgICByZXR1cm4gcDI7Ly9tYXRbbm9kZV09cDI7CgogICAgfQp9Cgp2b2lkIHVwZGF0ZShsb25nIGIsbG9uZyBlLGxvbmcgeCxsb25nIG5vZGUpCnsKICAgIGlmKHg+ZSB8fCB4PGIpCiAgICAgICAgcmV0dXJuOwogICAgLy8gaWYoYXJyW21hdFtub2RlXV0gPCBhcnJbeF0pCiAgICAgIC8vICAgICAgbWF0W25vZGVdPXg7CiAgICBlbHNlIGlmKGIhPWUpewogICAgICAgIGlmKGFyclttYXRbbm9kZV1dIDwgYXJyW3hdKQogICAgICAgICAgICBtYXRbbm9kZV09eDsKICAgICAgICB1cGRhdGUoYiwoYitlKS8yLHgsMipub2RlKTsKICAgICAgICB1cGRhdGUoKGIrZSkvMisxLGUseCwyKm5vZGUrMSk7CiAgICAgICAgLy9yZXR1cm47CiAgICB9CiAgICAvL3JldHVybjsKfQoKaW50IG1haW4oKQp7CiAgICBsb25nIG4scSxpLGoscDEscDIsbCxtLHRlbXA7CiAgICBjaGFyIGNoOwogICAgc2NhbmYoIiVsZCIsJm4pOwogICAgRk9SRShpLDEsbisxKQogICAgICAgIHNjYW5mKCIlbGxkIixhcnIraSk7CiAgICBhcnJbMF09MDsKICAgIHNjYW5mKCIlbGQiLCZxKTsKICAgIEZPUihpLDUqTikKICAgICAgICBtYXRbaV09LTE7CiAgICBpbml0aWFsaXNlKDEsbiwxKTsKICAgIHdoaWxlKHEtLSkKICAgIHsKICAgICAgICBjaW4+PmNoPj5pPj5qOwogICAgICAgIGlmKGNoPT0nVScpCiAgICAgICAgewogICAgICAgICAgICBhcnJbaV09ajsKICAgICAgICAgICAgdXBkYXRlKDEsbixpLDEpOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKGNoPT0nUScpCiAgICAgICAgewogICAgICAgICAgICBpZihpPmopCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHRlbXA9aTsKICAgICAgICAgICAgICAgIGk9ajsKICAgICAgICAgICAgICAgIGo9dGVtcDsKICAgICAgICAgICAgfQogICAgICAgICAgICBwMT1xdWVyeSgxLG4saSxqLDEpOwogICAgICAgICAgICBpZihwMT09aSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcDI9cXVlcnkoMSxuLGkrMSxqLDEpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYocDE9PWopCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHAyPXF1ZXJ5KDEsbixpLGotMSwxKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICBsPXF1ZXJ5KDEsbixpLHAxLTEsMSk7CiAgICAgICAgICAgICAgIG09cXVlcnkoMSxuLHAxKzEsaiwxKTsKICAgICAgICAgICAgICAgaWYoYXJyW2xdPj1hcnJbbV0pCiAgICAgICAgICAgICAgICAgICAgcDI9bDsKICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgcDI9bTsKICAgICAgICAgICAgfQogICAgICAgICAgICBwcmludGYoIiVsbGRcbiIsYXJyW3AxXSthcnJbcDJdKTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gMDsKfQo=