#include<bits/stdc++.h>
using namespace std;
#define ll long long int
struct g
{
ll me=INT_MIN,sme=INT_MIN;
};
vector <ll> a;
vector <g> tree;
void build_tree(ll node,ll s,ll e)
{
if(s==e)
{
tree[node].me=a[s];
tree[node].sme=INT_MIN;
}
else
{
ll m=(s+e)/2;
build_tree(node*2,s,m);
build_tree(node*2+1,m+1,e);
if(tree[node*2].me>tree[node*2+1].me)
{
tree[node].me=tree[node*2].me;
tree[node].sme=max(tree[node*2].sme,tree[node*2+1].me);
}
else
{
tree[node].me=tree[node*2+1].me;
tree[node].sme=max(tree[node*2+1].sme,tree[node*2].me);
}
}
}
void update_tree(ll node,ll s,ll e,ll idx,ll v)
{
if(s==e)
{
tree[node].me=max(tree[node].me,v);
tree[node].sme=INT_MIN;
}
else
{
ll m=(s+e)/2;
if(s<=idx&&idx<=m)
{
update_tree(node*2,s,m,idx,v);
}
else
{
update_tree(node*2+1,m+1,e,idx,v);
}
if(tree[node*2].me>tree[node*2+1].me)
{
tree[node].me=tree[node*2].me;
tree[node].sme=max(tree[node*2].sme,tree[node*2+1].me);
}
else
{
tree[node].me=tree[node*2+1].me;
tree[node].sme=max(tree[node*2+1].sme,tree[node*2].me);
}
}
}
g query_tree(ll node,ll s,ll e,ll l,ll r)
{
if(s>e||s>r||e<l)
{
g p;
return p;
}
else if(l<=s&&e<=r)
return tree[node];
else
{
ll m=(s+e)/2;
g p1,p2,p3;
p1=query_tree(node*2,s,m,l,r);
p2=query_tree(node*2+1,m+1,e,l,r);
if(p1.me>p2.me)
{
p3.me=p1.me;
p3.sme=max(p1.sme,p2.me);
}
else
{
p3.me=p2.me;
p3.sme=max(p2.sme,p1.me);
}
return p3;
}
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
a.resize(n);
tree.resize(4*n);
for(ll i=0;i<n;i++)
cin>>a[i];
build_tree(1,0,n-1);
ll q;
cin>>q;
while(q--)
{
char c;
cin>>c;
if(c=='U')
{
ll id,v;
cin>>id>>v;
update_tree(1,0,n-1,id-1,v);
}
else
{
ll l,r;
cin>>l>>r;
g res;
res=query_tree(1,0,n-1,l-1,r-1);
cout<< res.me+res.sme <<"\n";
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgbGwgbG9uZyBsb25nIGludAoKc3RydWN0IGcKewogICAgbGwgbWU9SU5UX01JTixzbWU9SU5UX01JTjsKfTsKCnZlY3RvciA8bGw+IGE7CnZlY3RvciA8Zz4gdHJlZTsKCnZvaWQgYnVpbGRfdHJlZShsbCBub2RlLGxsIHMsbGwgZSkKewogICBpZihzPT1lKQogICB7CiAgICAgICB0cmVlW25vZGVdLm1lPWFbc107CiAgICAgICB0cmVlW25vZGVdLnNtZT1JTlRfTUlOOwogICB9CiAgIGVsc2UKICAgewogICAgICAgbGwgbT0ocytlKS8yOwogICAgICAgYnVpbGRfdHJlZShub2RlKjIscyxtKTsKICAgICAgIGJ1aWxkX3RyZWUobm9kZSoyKzEsbSsxLGUpOwogICAgICAgaWYodHJlZVtub2RlKjJdLm1lPnRyZWVbbm9kZSoyKzFdLm1lKQogICAgICAgewogICAgICAgICAgIHRyZWVbbm9kZV0ubWU9dHJlZVtub2RlKjJdLm1lOwogICAgICAgICAgIHRyZWVbbm9kZV0uc21lPW1heCh0cmVlW25vZGUqMl0uc21lLHRyZWVbbm9kZSoyKzFdLm1lKTsKICAgICAgIH0KICAgICAgIGVsc2UKICAgICAgIHsKICAgICAgICAgICB0cmVlW25vZGVdLm1lPXRyZWVbbm9kZSoyKzFdLm1lOwogICAgICAgICAgIHRyZWVbbm9kZV0uc21lPW1heCh0cmVlW25vZGUqMisxXS5zbWUsdHJlZVtub2RlKjJdLm1lKTsKICAgICAgIH0KICAgfQp9Cgp2b2lkIHVwZGF0ZV90cmVlKGxsIG5vZGUsbGwgcyxsbCBlLGxsIGlkeCxsbCB2KQp7CiAgICBpZihzPT1lKQogICAgewogICAgICAgIHRyZWVbbm9kZV0ubWU9bWF4KHRyZWVbbm9kZV0ubWUsdik7CiAgICAgICAgdHJlZVtub2RlXS5zbWU9SU5UX01JTjsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBsbCBtPShzK2UpLzI7CiAgICAgICAgaWYoczw9aWR4JiZpZHg8PW0pCiAgICAgICAgewogICAgICAgICAgICB1cGRhdGVfdHJlZShub2RlKjIscyxtLGlkeCx2KTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgdXBkYXRlX3RyZWUobm9kZSoyKzEsbSsxLGUsaWR4LHYpOwogICAgICAgIH0KICAgICAgIGlmKHRyZWVbbm9kZSoyXS5tZT50cmVlW25vZGUqMisxXS5tZSkKICAgICAgIHsKICAgICAgICAgICB0cmVlW25vZGVdLm1lPXRyZWVbbm9kZSoyXS5tZTsKICAgICAgICAgICB0cmVlW25vZGVdLnNtZT1tYXgodHJlZVtub2RlKjJdLnNtZSx0cmVlW25vZGUqMisxXS5tZSk7CiAgICAgICB9CiAgICAgICBlbHNlCiAgICAgICB7CiAgICAgICAgICAgdHJlZVtub2RlXS5tZT10cmVlW25vZGUqMisxXS5tZTsKICAgICAgICAgICB0cmVlW25vZGVdLnNtZT1tYXgodHJlZVtub2RlKjIrMV0uc21lLHRyZWVbbm9kZSoyXS5tZSk7CiAgICAgICB9CiAgICB9Cn0KCmcgcXVlcnlfdHJlZShsbCBub2RlLGxsIHMsbGwgZSxsbCBsLGxsIHIpCnsKICAgIGlmKHM+ZXx8cz5yfHxlPGwpCiAgICB7CiAgICAgICAgZyBwOwogICAgICAgIHJldHVybiBwOwogICAgfQogICAgZWxzZSBpZihsPD1zJiZlPD1yKQogICAgICAgIHJldHVybiB0cmVlW25vZGVdOwogICAgZWxzZQogICAgewogICAgICAgIGxsIG09KHMrZSkvMjsKICAgICAgICBnIHAxLHAyLHAzOwogICAgICAgIHAxPXF1ZXJ5X3RyZWUobm9kZSoyLHMsbSxsLHIpOwogICAgICAgIHAyPXF1ZXJ5X3RyZWUobm9kZSoyKzEsbSsxLGUsbCxyKTsKICAgICAgIGlmKHAxLm1lPnAyLm1lKQogICAgICAgewogICAgICAgICAgIHAzLm1lPXAxLm1lOwogICAgICAgICAgIHAzLnNtZT1tYXgocDEuc21lLHAyLm1lKTsKICAgICAgIH0KICAgICAgIGVsc2UKICAgICAgIHsKICAgICAgICAgICBwMy5tZT1wMi5tZTsKICAgICAgICAgICBwMy5zbWU9bWF4KHAyLnNtZSxwMS5tZSk7CiAgICAgICB9CiAgICAgICByZXR1cm4gcDM7CiAgICB9Cn0KCmludCBtYWluKCkKewogICAgaW9zX2Jhc2UgOjogc3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBsbCBuOwogICAgY2luPj5uOwogICAgYS5yZXNpemUobik7CiAgICB0cmVlLnJlc2l6ZSg0Km4pOwogICAgZm9yKGxsIGk9MDtpPG47aSsrKQogICAgICAgIGNpbj4+YVtpXTsKICAgIGJ1aWxkX3RyZWUoMSwwLG4tMSk7CiAgICBsbCBxOwogICAgY2luPj5xOwogICAgd2hpbGUocS0tKQogICAgewogICAgICAgIGNoYXIgYzsKICAgICAgICBjaW4+PmM7CiAgICAgICAgaWYoYz09J1UnKQogICAgICAgIHsKICAgICAgICAgICAgbGwgaWQsdjsKICAgICAgICAgICAgY2luPj5pZD4+djsKICAgICAgICAgICAgdXBkYXRlX3RyZWUoMSwwLG4tMSxpZC0xLHYpOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBsbCBsLHI7CiAgICAgICAgICAgIGNpbj4+bD4+cjsKICAgICAgICAgICAgZyByZXM7CiAgICAgICAgICAgIHJlcz1xdWVyeV90cmVlKDEsMCxuLTEsbC0xLHItMSk7CiAgICAgICAgICAgIGNvdXQ8PCByZXMubWUrcmVzLnNtZSA8PCJcbiI7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0K