#include <cstdio>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <map>

#include <set>

#include <queue>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 500005

#define eps 1e-8

#define db double

#define L ch[x][0]

#define R ch[x][1]

#define ll long long

#define inf 0x3f3f3f3f

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

void Finout()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    freopen("wa.txt","w",stdout);

    #endif

}

int Getint()

{

    int x=0,f=1; char ch=getchar();

    while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}

    while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}

    return x*f;

}

int ch[maxn][2],sum[maxn],lx[maxn],rx[maxn],mx[maxn],fa[maxn],siz[maxn],v[maxn];

int a[maxn],n,rt,q,tot;

void update(int x)

{

	siz[x]=siz[L]+siz[R]+1;

	sum[x]=sum[L]+sum[R]+v[x];

	mx[x]=lx[x]=rx[x]=v[x];

	if (x==1)

	{

		mx[x]=mx[R];

		lx[x]=lx[R];

		rx[x]=rx[R];

		return ;

	}

	if (x==n+2)

	{

		mx[x]=mx[L];

		lx[x]=lx[L];

		rx[x]=rx[L];

		return ;

	}

	if (((!L))&&((!R))) lx[x]=rx[x]=mx[x]=sum[x]=v[x];

	else if ((!L))

	{

		lx[x]=max(v[x],v[x]+lx[R]);

		rx[x]=max(rx[R],sum[R]+v[x]);

		mx[x]=max(v[x],max(mx[R],v[x]+lx[R]));

		mx[x]=max(mx[x],max(lx[x],rx[x]));

	}

	else if ((!R))

	{

		lx[x]=max(lx[L],sum[L]+v[x]);

		rx[x]=max(v[x],v[x]+rx[L]);

		mx[x]=max(v[x],max(mx[L],rx[L]+v[x]));

		mx[x]=max(mx[x],max(lx[x],rx[x]));

	}

	else

	{

		lx[x]=max(lx[L],max(sum[L]+v[x],sum[L]+v[x]+lx[R]));

		rx[x]=max(rx[R],max(sum[R]+v[x],sum[R]+v[x]+rx[L]));

		mx[x]=max(mx[L],max(mx[R],max(rx[L],0)+v[x]+max(lx[R],0)));

		mx[x]=max(mx[x],max(lx[x],rx[x]));

	}

}

void rot(int x,int &k)

{

	int y=fa[x],z=fa[y],l,r;

	if (ch[y][0]==x) l=0; else l=1; r=l^1;

	if (y==k) k=x;

	else

	{

		if (ch[z][0]==y) ch[z][0]=x;

		else ch[z][1]=x;

	}

	fa[x]=z; fa[y]=x; fa[ch[x][r]]=y;

	ch[y][l]=ch[x][r];ch[x][r]=y;

	update(y); update(x);

}

void splay(int x,int &k)

{

	while (x!=k)

	{

		int y=fa[x],z=fa[y];

		if (y!=k)

		{

			if ((ch[z][0]==y)^(ch[y][0]==x)) rot(x,k);

			else rot(y,k);

		}

		rot(x,k);

	}

}

int find(int x,int f)

{

	if (f<=siz[L]) return find(L,f);

	else if (f==(siz[L]+1)) return x;

	else return find(R,f-siz[L]-1);

}

int build(int l,int r,int lst)

{

	int mid=l+r>>1;

	v[mid]=a[mid]; fa[mid]=lst;

	ch[mid][0]=l<mid?build(l,mid-1,mid):0;

	ch[mid][1]=r>mid?build(mid+1,r,mid):0;

	update(mid);

	return mid;

}

void debug()

{

	printf("The Tree's root is %d\n",rt);

	F(i,1,15) printf("Node %d : fa %d L %d R %d lx %d rx %d mx %d sum %d siz %d\n",i,fa[i],ch[i][0],ch[i][1],lx[i],rx[i],mx[i],sum[i],siz[i]);

}

int fx,fy;

int main()

{

	Finout();

	n=Getint();

	F(i,1,n) a[i+1]=Getint();

	rt=build(1,n+2,0); tot=n+2;

//	debug();

	q=Getint(); char opt[11];int x,y;

	F(i,1,q)

	{

		scanf("%s",opt);

		switch(opt[0])

		{

			case 'Q':

				x=Getint();y=Getint();

//				printf("%d %d\n",x,y);

				fx=find(rt,x),fy=find(rt,y+2);

//				printf("%d %d\n",fx,fy);

				splay(fx,rt); splay(fy,ch[fx][1]);

				printf("%d\n",mx[ch[ch[fx][1]][0]]);

				update(fy); update(fx);

			break;

			case 'I':

				++tot; x=Getint();y=Getint();

				v[tot]=y;

				fx=find(rt,x),fy=find(rt,x+1);

				splay(fx,rt);splay(fy,ch[fx][1]);

				fa[tot]=fy; ch[fy][0]=tot;

				update(tot); update(fy); update(fx);

			break;

			case 'R':

				x=Getint();y=Getint();

				fx=find(rt,x+1); splay(fx,rt);

				v[fx]=y;update(fx);

			break;

			case 'D':

				x=Getint();

				fx=find(rt,x); fy=find(rt,x+2);

				splay(fx,rt); splay(fy,ch[fx][1]);

				ch[fy][0]=0; update(fy); update(fx);

			break;

		}

//		debug();

	}

}