#include<cstdlib>
#include<cstdio>
#include<ctime>
int data[500005<<1],prev[500005<<1],next[500005<<1],first,second,middle;
inline int abs(int number){
	if(number<0){
		return -number;
	};
	return number;
};
inline int min(int first,int second){
	if(first<second){
		return first;
	};
	return second;
};
struct node{
	int size,randkey,value,left,right;
};
namespace treap1{
	int top,root,answer=2147483647;
	node tree[500005<<1];
	inline int newnode(int value){
		tree[++top].value=value;
		tree[top].size=1;
		tree[top].randkey=rand();
		return top;
	};
	inline void pushup(int root){
		tree[root].size=tree[tree[root].left].size+tree[tree[root].right].size+1;
		return;
	};
	inline void split(int root,int value,int &first,int &second){
		if(!root){
			first=second=0;
			return;
		};
		if(tree[root].value<=value){
			first=root;
			split(tree[root].right,value,tree[root].right,second);
		}else{
			second=root;
			split(tree[root].left,value,first,tree[root].left);
		};
		pushup(root);
		return;
	};
	inline int merge(int first,int second){
		if(!first||!second){
			return first+second;
		};
		if(tree[first].randkey>tree[second].randkey){
			tree[first].right=merge(tree[first].right,second);
			pushup(first);
			return first;
		};
		tree[second].left=merge(first,tree[second].left);
		pushup(second);
		return second;
	};
	inline int head(int root){
		while(tree[root].left){
			root=tree[root].left;
		};
		return tree[root].value;
	};
	inline int tail(int root){
		while(tree[root].right){
			root=tree[root].right;
		};
		return tree[root].value;
	};
	inline void insert(int value){
		split(root,value,first,second);
		if(tree[first].size){
			answer=min(answer,abs(value-head(first)));
		}else{
			answer=min(answer,abs(tail(second)-value));
		};
		root=merge(merge(first,newnode(value)),second);
		return;
	};
};
namespace treap2{
	node tree[500005<<1];
	int top,root;
	inline int newnode(int value){
		tree[++top].value=value;
		tree[top].size=1;
		tree[top].randkey=rand();
		return top;
	};
	inline void pushup(int root){
		tree[root].size=tree[tree[root].left].size+tree[tree[root].right].size+1;
		return;
	};
	inline void split(int root,int value,int &first,int &second){
		if(!root){
			first=second=0;
			return;
		};
		if(tree[root].value<=value){
			first=root;
			split(tree[root].right,value,tree[root].right,second);
		}else{
			second=root;
			split(tree[root].left,value,first,tree[root].left);
		};
		pushup(root);
	};
	inline int merge(int first,int second){
		if(!first||!second){
			return first+second;
		};
		if(tree[first].randkey>tree[second].randkey){
			tree[first].right=merge(tree[first].right,second);
			pushup(first);
			return first;
		};
		tree[second].left=merge(first,tree[second].left);
		pushup(second);
		return second;
	};
	inline void insert(int value){
		split(root,value,first,second);
		root=merge(merge(first,newnode(value)),second);
		return;
	};
	inline void erase(int value){
		split(root,value,first,second);
		split(first,value-1,first,middle);
		middle=merge(tree[middle].left,tree[middle].right);
		root=merge(merge(first,middle),second);
		return;
	};
	inline int head(int root){
		while(tree[root].left){
			root=tree[root].left;
		};
		return tree[root].value;
	};
};
int main(int argc,char **argv){
	srand(time(0));
	int size,action;
	scanf("%d %d",&size,&action);
	for(int iter=1;iter<=size;++iter){
		scanf("%d",&data[iter]);
		treap1::insert(data[iter]);
	};
	for(int iter=1;iter<size;++iter){
		treap2::insert(abs(data[iter+1]-data[iter]));
		next[iter]=iter+1;
	};
	for(int iter=2;iter<=size;++iter){
		prev[iter]=iter-1;
	};
	prev[size+1]=size;
	int count=size;
	do{
		char str[55];
		scanf("%s",str);
		if(str[0]=='I'){
			int dot,value;
			scanf("%d %d",&dot,&value);
			if(dot<size){
				treap2::erase(abs(data[dot+1]-data[prev[dot+1]]));
			};
			treap2::insert(abs(data[prev[dot+1]]-value));
			if(dot<size){
				treap2::insert(abs(value-data[dot+1]));
			};
			data[++count]=value;
			prev[count]=prev[dot+1];
			next[count]=dot+1;
			next[prev[dot+1]]=count;
			prev[dot+1]=count;
			treap1::insert(value);
		}else if(str[4]=='S'){
			printf("%d\n",treap2::head(treap2::root));
		}else{
			printf("%d\n",treap1::answer);
		};
	}while(--action);
	return 0;
};

全 WA。