P1110

delicious

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
multiset<int>delta,full;
int st[500100],ed[500100];
int srt=inf;
int n,m;
void update_srt(int x){
	multiset<int>::iteratorit=full.lower_bound(x);
	intnw=*it-x;
	--it;
	nw=min(nw,x-*it);
	srt=min(srt,nw);
	full.insert(x);
}
void replac(int pos,int x){
	delta.insert(abs(x-ed[pos]));
	if(pos!=n) delta.erase(delta.find(abs(st[pos+1]-ed[pos]))), delta.insert(abs(st[pos+1]-x));
	ed[pos]=x;
}
int getint(){
	intret=0,fix=1;
	charch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')fix=-1;
		ch=getchar();
	}
	while(isdigit(ch))ret=ret*10+(ch-'0'),ch=getchar();
	return ret*fix;
}
int main(){
	static char str[1<<5];
	n=getint(),m=getint();
	for(int i=1;i<=n;i++)st[i]=ed[i]=getint();
	full.insert(inf),full.insert(-inf);
	for(int i=1;i<n;i++)delta.insert(abs(st[i+1]-ed[i]));
	for(int i=1;i<=n;i++)update_srt(st[i]);
	for(int i=1,pos,x;i<=m;i++){
		scanf("%s",str);
		if(*str=='I'){
			pos=getint(),x=getint();
			update_srt(x);
			replac(pos,x);
		}else if(str[4]=='S')printf("%d\n",srt);
		else printf("%d\n",*delta.begin());
	}
	return 0;
}