#include<bits/stdc++.h>
using namespace std;
const int N = 40000010;
int c[N][2],val[N],rnd[N],si[N],tot,n,m;
long long mx[N],lmx[N],rmx[N],sum[N];
int read(){
	int x = 0,f = 0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}
void pushup(int x)
{
	si[x] = si[c[x][0]] + si[c[x][1]] + 1;
	sum[x] = val[x] + sum[c[x][1]] + sum[c[x][0]];
	mx[x] = max(max(mx[c[x][1]],mx[c[x][0]]),rmx[c[x][0]]+val[x]+lmx[c[x][1]]);
	lmx[x] = max(lmx[c[x][0]],sum[c[x][0]]+val[x]+lmx[c[x][1]]);
	rmx[x] = max(rmx[c[x][1]],sum[c[x][1]]+val[x]+rmx[c[x][0]]);
}
int newnode(int v){
	si[++tot] = 1;
	lmx[tot] = rmx[tot] = max(v,0);
	sum[tot] = mx[tot] = val[tot] = v;
	rnd[tot] = rand();
	return tot;
}
int merge(int x,int y)
{
	if(!x||!y) return x|y;
	if(rnd[x] < rnd[y]){
		c[x][1] = merge(c[x][1],y);
		pushup(x);
		return x;
	} 
	else{
		c[y][0] = merge(x,c[y][0]);
		pushup(y);
		return y;
	}
}
void split(int now,int k,int &x,int &y)
{
	if(!now) x = y = 0;
	else{
		if(k <= si[c[now][0]])
		{
			y = now;
			split(c[now][0],k,x,c[now][0]);
		}
		else{
			x = now;
			split(c[now][1],k-si[c[now][0]]-1,c[now][1],y);
		}
		pushup(now);
	}
}
int rt;
int main()
{
	n = read();
	for(int i = 1;i <= n;i++)
	{
		int a = read();
		rt = merge(rt,newnode(a));
	}	
	m = read();
	mx[0] = -0x3f3f3f3f3f3f3f3f;
	while(m--)
	{
		char opt[10];
		scanf("%s",opt);
		if(opt[0] == 'I')
		{
			int a = read(),b = read(),r1,r2;
			split(rt,a-1,r1,r2);
			rt = merge(r1,merge(newnode(b),r2));
		}
		if(opt[0] == 'D')
		{
			int a = read(),r1,r2,r3;
			split(rt,a-1,r1,r3);
			split(r3,1,r2,r3);
			rt = merge(r1,r3);
		}
		if(opt[0] == 'R')
		{
			int a = read(),b = read(),r1,r2,r3;
			split(rt,a-1,r1,r3);
			split(r3,1,r2,r3);
			val[r2] = b;
			pushup(r2);
			rt = merge(r1,merge(r2,r3));	
		}
		if(opt[0] == 'Q')
		{
			int a = read(),b = read(),r1,r2,r3;
			split(rt,b,r1,r3);
			split(r1,a-1,r1,r2);
			printf("%lld\n",mx[r2]);
			rt = merge(r1,merge(r2,r3));
		}
	}
	return 0;
}