#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,lst=-1,root[3],a[3][1100005],b[3][1100005],c[3][1100005],l[3][1100005],r[3][1100005],cnt[3],nm[3],xx,ll,rr;
vector<int> p[500005];
char s[15];
int merge(int cn,int x,int y)
{
	if (x && y)
	{
		if (c[cn][x]<c[cn][y])
		{
			r[cn][x]=merge(cn,r[cn][x],y);
			b[cn][x]=b[cn][l[cn][x]]+b[cn][r[cn][x]]+1;
			return x;
		}
		else
		{
			l[cn][y]=merge(cn,x,l[cn][y]);
			b[cn][y]=b[cn][l[cn][y]]+b[cn][r[cn][y]]+1;
			return y;
		}
	}
	else
	return x+y;
}
void split(int cn,int x,int &y,int &z,int k)
{
	if (x)
	{
		if (a[cn][x]<=k)
		{
			y=x;
			split(cn,r[cn][x],r[cn][x],z,k);
		}
		else
		{
			z=x;
			split(cn,l[cn][x],y,l[cn][x],k);
		}
		b[cn][x]=b[cn][l[cn][x]]+b[cn][r[cn][x]]+1;
	}
	else
	{
		y=0;
		z=0;
	}
}
int kth(int cn,int x,int k)
{
	if (k<=b[cn][l[cn][x]])
	return kth(cn,l[cn][x],k);
	else if (k==b[cn][l[cn][x]]+1)
	return a[cn][x];
	else
	return kth(cn,r[cn][x],k-b[cn][l[cn][x]]-1);
}
void insert(int cn,int num)
{
	int x,y;
	a[cn][++cnt[cn]]=num;
	b[cn][cnt[cn]]=1;
	c[cn][cnt[cn]]=rand();
	split(cn,root[cn],x,y,num-1);
	root[cn]=merge(cn,merge(cn,x,cnt[cn]),y);
	++nm[cn];
}
void erase(int cn,int num)
{
	int x,y,z;
	split(cn,root[cn],x,z,num);
	split(cn,x,x,y,num-1);
	y=merge(cn,l[cn][y],r[cn][y]);
	root[cn]=merge(cn,merge(cn,x,y),z);
	--nm[cn];
}
int rnk(int cn,int num)
{
	int x,y,result;
	split(cn,root[cn],x,y,num-1);
	result=b[cn][x]+1;
	root[cn]=merge(cn,x,y);
	return result;
}
int pre(int cn,int num)
{
	int x,y,result;
	split(cn,root[cn],x,y,num-1);
	result=kth(cn,x,b[cn][x]);
	root[cn]=merge(cn,x,y);
	return result;
}
int nxt(int cn,int num)
{
	int x,y,result;
	split(cn,root[cn],x,y,num);
	result=kth(cn,y,1);
	root[cn]=merge(cn,x,y);
	return result;
}
void print(int x)
{
	if (l[1][x])
	print(l[1][x]);
	if (lst!=-1)
	insert(2,a[1][x]-lst);
	lst=a[1][x];
	if (r[1][x])
	print(r[1][x]);
}
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;++i)
	{
		scanf("%d",&x);
		p[i].push_back(x);
		if (i>1)
		insert(0,abs(p[i][0]-p[i-1][0]));
		insert(1,x);
	}
	print(root[1]);
	while (m--)
	{
		cin>>s;
		if (s[4]=='R')
		{
			scanf("%d%d",&x,&y);
			if (x<n)
			erase(0,abs(p[x+1][0]-p[x][p[x].size()-1]));
			insert(0,abs(y-p[x][p[x].size()-1]));
			if (x<n)
			insert(0,abs(p[x+1][0]-y));
			p[x].push_back(y);
			xx=rnk(1,y);
			ll=kth(1,root[1],xx-1);
			rr=kth(1,root[1],xx);
			if (1<xx && xx<=nm[1])
			erase(2,rr-ll);
			if (xx>1)
			insert(2,y-ll);
			if (xx<=nm[1])
			insert(2,rr-y);
			insert(1,y);
		}
		else if (s[4]=='G')
		cout<<kth(0,root[0],1)<<'\n';
		else
		cout<<kth(2,root[2],1)<<'\n';
	}
}