/*
  Author: EnderDeer
  Online Judge: Luogu
*/

#include<bits/stdc++.h>

#define int long long
#define mem(x) memset(x,0,sizeof(x))

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

struct Treap{
	
	struct node{
		int l;
		int r;
		int w;
		int key;
		int siz;
	}e[2000010];
	
	int cnt,rt;
	
	int newnode(int w){
		cnt ++;
		e[cnt].w = w;
		e[cnt].key = rand();
		e[cnt].siz = 1;
		return cnt; 
	}
	
	void update(int i){
		e[i].siz = e[e[i].l].siz + e[e[i].r].siz + 1;
	}
	
	void split(int i,int w,int &x,int &y){
		if(!i){
			x = y = 0;
			return ;
		}
		if(e[i].w <= w){
			x = i;
			split(e[i].r,w,e[i].r,y);
		}
		else {
			y = i;
			split(e[i].l,w,x,e[i].l);
		}
		update(i);
	}
	
	int merge(int x,int y){
		if(!x || !y)return x + y;
		if(e[x].key > e[y].key){
			e[x].r = merge(e[x].r,y);
			update(x);
			return x;
		}
		else {
			e[y].l = merge(x,e[y].l);
			update(y);
			return y;
		}
	}
	
	int x,y,z;
	
	bool is_exist(int w){
		bool ans;
		split(rt,w,x,z);
		split(x,w - 1,x,y);
		if(!y)ans = false;
		else ans = true;
		rt = merge(x,merge(y,z));
		return ans;
	}
	
	void ins(int w){
		split(rt,w,x,y);
		rt = merge(merge(x,newnode(w)),y);
	}
	
	void del(int w){
		split(rt,w,x,z);
		split(x,w - 1,x,y);
		y = merge(e[y].l,e[y].r);
		rt = merge(merge(x,y),z);
	}
	
	int getnum(int rk){
		int now = rt;
		while(now){
			if(e[e[now].l].siz + 1 == rk)break;
			else if(e[e[now].l].siz >= rk)now = e[now].l;
			else {
				rk -= e[e[now].l].siz + 1;
				now = e[now].r;
			}
		}
		return e[now].w;
	}
	
	int pre(int w){
		ins(-2147483647);
		split(rt,w - 1,x,y);
		int now = x;
		while(e[now].r)now = e[now].r;
		int ans = e[now].w;
		rt = merge(x,y);
		del(-2147483647);
		return ans;
	}
	
	int nxt(int w){
		ins(2147483647);
		split(rt,w,x,y);
		int now = y;
		while(e[now].l)now = e[now].l;
		int ans = e[now].w;
		rt = merge(x,y);
		del(2147483647);
		return ans;
	}
}t1,t2;//t1是原来的元素，t2是差 

int n,m;
int a[2000010];
int b[2000010];
int minsortgap = 2147483647;
int tot;

signed main(){
	cin>>n>>m;
	for(int i = 1;i <= n;i ++)a[i] = read(),b[i] = a[i];
	t1.ins(a[n]);
	for(int i = 1;i <= n - 1;i ++){
		t1.ins(a[i]);
		t2.ins(abs(a[i + 1] - a[i]));
		tot ++;
	}
	for(int i = 1;i <= n;i ++)minsortgap = min(minsortgap,min(a[i] - t1.pre(a[i]),t1.nxt(a[i]) - a[i]));
	while(m --){
		string op;
		int i,k;
		op.resize(6);
		scanf("%s",&op[0]);
		if(op == "INSERT"){
			i = read(),k = read();
			if(i == n){
				if(t1.is_exist(k))minsortgap = 0;
				else minsortgap = min(minsortgap,min(k - t1.pre(k),t1.nxt(k) - k));
				t1.ins(k);
				t2.ins(k - b[i]);
				tot ++;
				b[i] = k;
				continue; 
			}
			t2.del(abs(b[i] - a[i + 1]));
			if(t1.is_exist(k))minsortgap = 0;
			else minsortgap = min(minsortgap,min(k - t1.pre(k),t1.nxt(k) - k));
			t1.ins(k);
			t2.ins(abs(k - b[i]));
			t2.ins(abs(a[i + 1] - k));
			tot ++;
			b[i] = k;
		}
		if(op == "MIN_GA"){
			printf("%lld\n",t2.getnum(1));
		}
		if(op == "MIN_SO"){
			printf("%lld\n",minsortgap);
		}
	}
	return 0;
}