import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.*;
class KGSS{
static class FastReader
{
public FastReader()
{
}
{
while (st == null || !st.hasMoreElements())
{
try
{
}
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
}
long nextLong()
{
return Long.
parseLong(next
()); }
double nextDouble()
{
return Double.
parseDouble(next
()); }
{
try
{
str = br.readLine();
}
{
e.printStackTrace();
}
return str;
}
}
public static void main
(String args
[]){ FastReader sc=new FastReader();
int n=sc.nextInt();
int a[]=new int[n+1];
int tree[]=new int[4*n+1];
int asli_tree[]=new int[4*n+1];
for(int i=1;i<n+1;i++)
{a[i]=sc.nextInt();}
builtTree(1,n,a,tree,asli_tree,1);
int q=sc.nextInt();
while(q-->0){
int x=sc.nextInt();
int y=sc.nextInt();
if(z.equals("Q"))
{System.
out.
println(query
(x,y,
1,n,tree,asli_tree,
1,
1));} if(z.equals("U"))
{update(y,x,0,n,tree,asli_tree,1);}
}
}
public static void builtTree(int s,int e,int a[],int tree[],int asli_tree[],int index){
if(s>e)
{return;}
if(s==e)
{tree[index]=a[s];
asli_tree[index]=a[s];
return;}
builtTree(s,(s+e)/2,a,tree,asli_tree,index*2);
builtTree((s+e)/2+1,e,a,tree,asli_tree,index*2+1);
tree
[index
]=Math.
max(tree
[2*index
],tree
[2*index
+1]); asli_tree
[index
]=Math.
max(tree
[2*index
]+tree
[2*index
+1],
Math.
max(asli_tree
[2*index
],asli_tree
[2*index
+1]));
}
public static int query(int qs,int qe,int s,int e,int tree[],int asli_tree[],int index,int i){
if(qs>e || qe<s)
{return 0;}
if(qs<=s && qe>=e && i==0)
{return tree[index];}
if(qs<=s && qe>=e && i==1)
{return asli_tree[index];}
int left=query(qs,qe,s,(s+e)/2,tree,asli_tree,index*2,0);//tree
int left1=query(qs,qe,s,(s+e)/2,tree,asli_tree,index*2,1);//asli_tree
int right=query(qs,qe,(s+e)/2+1,e,tree,asli_tree,index*2+1,0);
int right1=query(qs,qe,(s+e)/2+1,e,tree,asli_tree,index*2+1,1);
if(index!=1 && i==0)
{return Math.
max(left,right
);} if(index!=1 && i==1)
{return Math.
max(left
+right,
Math.
max(left1,right1
));} return Math.
max(left
+right,
Math.
max(left1,right1
)); }
public static void update(int value,int i,int s,int e,int tree[],int asli_tree[],int index){
if(i<s || i>e)
{return;}
if(s==e)
{tree[index]=value;
asli_tree[index]=value;
return;}
update(value,i,s,(s+e)/2,tree,asli_tree,index*2);
update(value,i,(s+e)/2+1,e,tree,asli_tree,index*2+1);
tree
[index
]=Math.
max(tree
[2*index
],tree
[2*index
+1]); asli_tree
[index
]=Math.
max(tree
[2*index
]+tree
[2*index
+1],
Math.
max(asli_tree
[2*index
],asli_tree
[2*index
+1])); }
}
aW1wb3J0IGphdmEuaW8uQnVmZmVyZWRSZWFkZXI7IAppbXBvcnQgamF2YS5pby5JT0V4Y2VwdGlvbjsgCmltcG9ydCBqYXZhLmlvLklucHV0U3RyZWFtUmVhZGVyOyAKaW1wb3J0IGphdmEudXRpbC5TY2FubmVyOyAKaW1wb3J0IGphdmEudXRpbC5TdHJpbmdUb2tlbml6ZXI7CmltcG9ydCBqYXZhLnV0aWwuKjsKY2xhc3MgS0dTU3sKICAgc3RhdGljIGNsYXNzIEZhc3RSZWFkZXIgCiAgICB7IAogICAgICAgIEJ1ZmZlcmVkUmVhZGVyIGJyOyAKICAgICAgICBTdHJpbmdUb2tlbml6ZXIgc3Q7IAogCiAgICAgICAgcHVibGljIEZhc3RSZWFkZXIoKSAKICAgICAgICB7IAogICAgICAgICAgICBiciA9IG5ldyBCdWZmZXJlZFJlYWRlcihuZXcKICAgICAgICAgICAgICAgICAgICAgSW5wdXRTdHJlYW1SZWFkZXIoU3lzdGVtLmluKSk7IAogICAgICAgIH0gCiAKICAgICAgICBTdHJpbmcgbmV4dCgpIAogICAgICAgIHsgCiAgICAgICAgICAgIHdoaWxlIChzdCA9PSBudWxsIHx8ICFzdC5oYXNNb3JlRWxlbWVudHMoKSkgCiAgICAgICAgICAgIHsgCiAgICAgICAgICAgICAgICB0cnkKICAgICAgICAgICAgICAgIHsgCiAgICAgICAgICAgICAgICAgICAgc3QgPSBuZXcgU3RyaW5nVG9rZW5pemVyKGJyLnJlYWRMaW5lKCkpOyAKICAgICAgICAgICAgICAgIH0gCiAgICAgICAgICAgICAgICBjYXRjaCAoSU9FeGNlcHRpb24gIGUpIAogICAgICAgICAgICAgICAgeyAKICAgICAgICAgICAgICAgICAgICBlLnByaW50U3RhY2tUcmFjZSgpOyAKICAgICAgICAgICAgICAgIH0gCiAgICAgICAgICAgIH0gCiAgICAgICAgICAgIHJldHVybiBzdC5uZXh0VG9rZW4oKTsgCiAgICAgICAgfSAKIAogICAgICAgIGludCBuZXh0SW50KCkgCiAgICAgICAgeyAKICAgICAgICAgICAgcmV0dXJuIEludGVnZXIucGFyc2VJbnQobmV4dCgpKTsgCiAgICAgICAgfSAKIAogICAgICAgIGxvbmcgbmV4dExvbmcoKSAKICAgICAgICB7IAogICAgICAgICAgICByZXR1cm4gTG9uZy5wYXJzZUxvbmcobmV4dCgpKTsgCiAgICAgICAgfSAKIAogICAgICAgIGRvdWJsZSBuZXh0RG91YmxlKCkgCiAgICAgICAgeyAKICAgICAgICAgICAgcmV0dXJuIERvdWJsZS5wYXJzZURvdWJsZShuZXh0KCkpOyAKICAgICAgICB9IAogCiAgICAgICAgU3RyaW5nIG5leHRMaW5lKCkgCiAgICAgICAgeyAKICAgICAgICAgICAgU3RyaW5nIHN0ciA9ICIiOyAKICAgICAgICAgICAgdHJ5CiAgICAgICAgICAgIHsgCiAgICAgICAgICAgICAgICBzdHIgPSBici5yZWFkTGluZSgpOyAKICAgICAgICAgICAgfSAKICAgICAgICAgICAgY2F0Y2ggKElPRXhjZXB0aW9uIGUpIAogICAgICAgICAgICB7IAogICAgICAgICAgICAgICAgZS5wcmludFN0YWNrVHJhY2UoKTsgCiAgICAgICAgICAgIH0gCiAgICAgICAgICAgIHJldHVybiBzdHI7IAogICAgICAgIH0gCiAgICB9IAogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nIGFyZ3NbXSl7CiAgICAgICAgRmFzdFJlYWRlciBzYz1uZXcgRmFzdFJlYWRlcigpOyAKICAgICAgICBpbnQgbj1zYy5uZXh0SW50KCk7CiAgICAgICAgaW50IGFbXT1uZXcgaW50W24rMV07CiAgICAgICAgaW50IHRyZWVbXT1uZXcgaW50WzQqbisxXTsKICAgICAgICBpbnQgYXNsaV90cmVlW109bmV3IGludFs0Km4rMV07CiAKICAgICAgICBmb3IoaW50IGk9MTtpPG4rMTtpKyspCiAgICAgICAge2FbaV09c2MubmV4dEludCgpO30KICAgICAgICAgYnVpbHRUcmVlKDEsbixhLHRyZWUsYXNsaV90cmVlLDEpOwogCiAgICAgICAgaW50IHE9c2MubmV4dEludCgpOwogICAgICAgIHdoaWxlKHEtLT4wKXsKIAogICAgICAgIFN0cmluZyB6PXNjLm5leHQoKTsKICAgICAgICBpbnQgeD1zYy5uZXh0SW50KCk7CiAgICAgICAgaW50IHk9c2MubmV4dEludCgpOwogICAgICAgIGlmKHouZXF1YWxzKCJRIikpCiAgICAgICAge1N5c3RlbS5vdXQucHJpbnRsbihxdWVyeSh4LHksMSxuLHRyZWUsYXNsaV90cmVlLDEsMSkpO30KICAgICAgICBpZih6LmVxdWFscygiVSIpKQogICAgICAgIHt1cGRhdGUoeSx4LDAsbix0cmVlLGFzbGlfdHJlZSwxKTt9CiAgICB9CiAgIH0KICAgcHVibGljIHN0YXRpYyB2b2lkIGJ1aWx0VHJlZShpbnQgcyxpbnQgZSxpbnQgYVtdLGludCB0cmVlW10saW50IGFzbGlfdHJlZVtdLGludCBpbmRleCl7CiAgICAgIGlmKHM+ZSkKICAgICAge3JldHVybjt9CiAgICAgIGlmKHM9PWUpCiAgICAgIHt0cmVlW2luZGV4XT1hW3NdOwogICAgICAgIGFzbGlfdHJlZVtpbmRleF09YVtzXTsKICAgIHJldHVybjt9CiAKICAgICAgYnVpbHRUcmVlKHMsKHMrZSkvMixhLHRyZWUsYXNsaV90cmVlLGluZGV4KjIpOwogICAgICBidWlsdFRyZWUoKHMrZSkvMisxLGUsYSx0cmVlLGFzbGlfdHJlZSxpbmRleCoyKzEpOwogCiAgICAgIHRyZWVbaW5kZXhdPU1hdGgubWF4KHRyZWVbMippbmRleF0sdHJlZVsyKmluZGV4KzFdKTsKICAgICAgYXNsaV90cmVlW2luZGV4XT1NYXRoLm1heCh0cmVlWzIqaW5kZXhdK3RyZWVbMippbmRleCsxXSxNYXRoLm1heChhc2xpX3RyZWVbMippbmRleF0sYXNsaV90cmVlWzIqaW5kZXgrMV0pKTsKIAogICAgfQogICBwdWJsaWMgc3RhdGljIGludCBxdWVyeShpbnQgcXMsaW50IHFlLGludCBzLGludCBlLGludCB0cmVlW10saW50IGFzbGlfdHJlZVtdLGludCBpbmRleCxpbnQgaSl7CiAgICAgIGlmKHFzPmUgfHwgcWU8cykKICAgICAge3JldHVybiAwO30KICAgICAgaWYocXM8PXMgJiYgcWU+PWUgJiYgaT09MCkgCiAgICAgIHtyZXR1cm4gdHJlZVtpbmRleF07fQogICAgICBpZihxczw9cyAmJiBxZT49ZSAmJiBpPT0xKSAKICAgICAge3JldHVybiBhc2xpX3RyZWVbaW5kZXhdO30KICAgICAgaW50IGxlZnQ9cXVlcnkocXMscWUscywocytlKS8yLHRyZWUsYXNsaV90cmVlLGluZGV4KjIsMCk7Ly90cmVlCiAgICAgIGludCBsZWZ0MT1xdWVyeShxcyxxZSxzLChzK2UpLzIsdHJlZSxhc2xpX3RyZWUsaW5kZXgqMiwxKTsvL2FzbGlfdHJlZQogICAgICBpbnQgcmlnaHQ9cXVlcnkocXMscWUsKHMrZSkvMisxLGUsdHJlZSxhc2xpX3RyZWUsaW5kZXgqMisxLDApOwogICAgICBpbnQgcmlnaHQxPXF1ZXJ5KHFzLHFlLChzK2UpLzIrMSxlLHRyZWUsYXNsaV90cmVlLGluZGV4KjIrMSwxKTsKIAogICAgICBpZihpbmRleCE9MSAmJiBpPT0wKQogICAgICB7cmV0dXJuIE1hdGgubWF4KGxlZnQscmlnaHQpO30KICAgICAgaWYoaW5kZXghPTEgJiYgaT09MSkKICAgICAge3JldHVybiBNYXRoLm1heChsZWZ0K3JpZ2h0LE1hdGgubWF4KGxlZnQxLHJpZ2h0MSkpO30KICAgICAgcmV0dXJuIE1hdGgubWF4KGxlZnQrcmlnaHQsTWF0aC5tYXgobGVmdDEscmlnaHQxKSk7CiAgICB9IAogICBwdWJsaWMgc3RhdGljIHZvaWQgdXBkYXRlKGludCB2YWx1ZSxpbnQgaSxpbnQgcyxpbnQgZSxpbnQgdHJlZVtdLGludCBhc2xpX3RyZWVbXSxpbnQgaW5kZXgpewogICAgICBpZihpPHMgfHwgaT5lKQogICAgICB7cmV0dXJuO30KICAgICAgaWYocz09ZSkKICAgICAge3RyZWVbaW5kZXhdPXZhbHVlOwogICAgICAgIGFzbGlfdHJlZVtpbmRleF09dmFsdWU7CiAgICByZXR1cm47fQogICAgICB1cGRhdGUodmFsdWUsaSxzLChzK2UpLzIsdHJlZSxhc2xpX3RyZWUsaW5kZXgqMik7CiAgICAgIHVwZGF0ZSh2YWx1ZSxpLChzK2UpLzIrMSxlLHRyZWUsYXNsaV90cmVlLGluZGV4KjIrMSk7CiAgICAgIHRyZWVbaW5kZXhdPU1hdGgubWF4KHRyZWVbMippbmRleF0sdHJlZVsyKmluZGV4KzFdKTsKICAgICAgYXNsaV90cmVlW2luZGV4XT1NYXRoLm1heCh0cmVlWzIqaW5kZXhdK3RyZWVbMippbmRleCsxXSxNYXRoLm1heChhc2xpX3RyZWVbMippbmRleF0sYXNsaV90cmVlWzIqaW5kZXgrMV0pKTsKICAgIH0KfQ==