#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
inline int read(){
	int s=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)){
		s=s*10-48+ch;
		ch=getchar();
	}
	return s;
}
int tr[MAXN][2],val[MAXN],cv[MAXN],siz[MAXN],cnt;
int n,m,a[500001],pre[500001],rt,A2=(1<<30),RT;
inline int Min(int x,int y){return x<y?x:y;}
char O[20];
int t[MAXN][2],v[MAXN],C[MAXN],tot;
const int inf=(1<<30);
int A3=(1<<30),b[500001];
inline void pushup(int x){siz[x]=siz[tr[x][0]]+siz[tr[x][1]]+1;}
inline int rd(){return rand()<<15|rand();}
inline int BD(int x){
	v[++tot]=x;
	C[tot]=rd();
	return tot;
}
inline int bd(int x){
	val[++cnt]=x;
	siz[cnt]=1;
	cv[cnt]=rd();
	return cnt;
}
void split(int now,int k,int &x,int &y){
	if(!now){x=y=0;return;}
	if(val[now]<=k)x=now,split(tr[now][1],k,tr[now][1],y);
	else y=now,split(tr[now][0],k,x,tr[now][0]);
	pushup(now);
}
void Split(int now,int k,int &x,int &y){
	if(!now){x=y=0;return;}
	if(v[now]<=k)x=now,Split(t[now][1],k,t[now][1],y);
	else y=now,Split(t[now][0],k,x,t[now][0]);
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(cv[x]<cv[y]){
		tr[x][1]=merge(tr[x][1],y);
		pushup(x);return x;
	}
	else{
		tr[y][0]=merge(x,tr[y][0]);
		pushup(y);return y;
	}
}
int Merge(int x,int y){
	if(!x||!y)return x+y;
	if(C[x]<C[y]){
		t[x][1]=Merge(t[x][1],y);
		return x;
	}
	else{
		t[y][0]=Merge(x,t[y][0]);
		return y;
	}
}
inline int Abs(int x){
	if(x<0)x=-x;
	return x;
}
int kth(int now,int k){
	if(k<=siz[tr[now][0]])return kth(tr[now][0],k);
	else if(k==siz[tr[now][0]]+1)return now;
	else return kth(tr[now][1],k-siz[tr[now][0]]-1);
}
void del(int vv){
	int x,y,z;
	Split(RT,vv,x,z);
	Split(x,vv-1,x,y);
	y=Merge(t[y][0],t[y][1]);
	RT=Merge(Merge(x,y),z);
}
int P(int vv){
	int x,y;
	split(rt,vv,x,y);
	int G=val[kth(x,siz[x])];
	rt=merge(x,y);
	return G;
}
int L(int vv){
	int x,y;
	split(rt,vv-1,x,y);
	int G=val[kth(y,1)];
	rt=merge(x,y);
	return G;
}
void Ins(int vv){
	int x,y;
	split(rt,vv,x,y);
	rt=merge(merge(x,bd(vv)),y);
}
void Insert(int vv){
	int x,y;
	Split(RT,vv,x,y);
	RT=Merge(Merge(x,BD(vv)),y);
}
int main(){
	srand(time(0));
	Ins(-inf);Ins(inf);
	n=read();m=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
		b[i]=a[i];
		pre[i]=a[i];
		Ins(a[i]);
	}
	sort(b+1,b+n+1);
	for(int i=1;i<n;++i){A3=Min(A3,b[i+1]-b[i]);Insert(Abs(a[i+1]-a[i]));Ins(a[i]);}
	Ins(a[n]);
	for(;m;m--){
		scanf("%s",O);
		if(O[0]=='I'){
			int A,B;
			A=read(),B=read();
			del(Abs(pre[A]-a[A+1]));
			Insert(Abs(B-pre[A]));
			Insert(Abs(B-a[A+1]));
			pre[A]=B;
			int T=RT;
			while(t[T][0])T=t[T][0];
			A2=v[T];
			int PB=P(B),LB=L(B);
			Ins(B);
			int R=Min(B-PB,LB-B);
			A3=Min(A3,R);
		}
		else if(O[4]=='G'){printf("%d\n",A2);}
		else{printf("%d\n",A3);}
	}
	return 0;
}

蒟蒻被卡空间了……求助awa