#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <time.h>
#define inf 1034567890

using namespace std;

struct BST{
	int l, r;
	int dat, val;
	int cnt, size;
}a[1000006], c[1000006];

struct node{
	int val, l, r;
}b[1000005];

int la[500005], tot, n, m, k, root = 1, tot1, root1 = 1, minn = inf;
char s[15];

inline int New(int val){
	a[++tot].val = val;
	a[tot].dat = rand();
	a[tot].cnt = a[tot].size = 1;
	return tot;
}

inline void update(int p){
	a[p].size = a[a[p].l ].size + a[a[p].r ].size + a[p].cnt ;
}

inline void zig(int &p){
	int q = a[p].l ;
	a[p].l = a[q].r;
	a[q].r = p;
	p = q;
	update(a[p].r );
	update(p);
}

inline void zag(int &p){
	int q = a[p].r ;
	a[p].r = a[q].l ;
	a[q].l = p;
	p = q;
	update(a[p].l );
	update(p);
}

inline void insert(int &p, int val){
	if(!p){
		p = New(val);
		return ;
	}
	if(val == a[p].val ){
		a[p].cnt ++;
		update(p);
		return ;
	}
	else if(val < a[p].val ){
		insert(a[p].l , val);
		if(a[p].dat < a[a[p].l ].dat ) zig(p);
	}
	else {
		insert(a[p].r , val);
		if(a[p].dat < a[a[p].r ].dat ) zag(p);
	}
	update(p);
}

inline void remove(int &p, int val){
	if(!p) return ;
	if(a[p].val == val){
		if(a[p].cnt > 1) {
			a[p].cnt --;
			update(p);
			return ;
		}
		if(a[p].l || a[p].r){
			if(!a[p].r || a[a[p].l ].dat > a[a[p].r ].dat )
			zig(p), remove(a[p].l , val);
			else zag(p), remove(a[p].r , val);
			update(p);
		}
		else p = 0;
	}
	if(val < a[p].val ){
		remove(a[p].l , val);
	}
	else remove(a[p].r , val);
	update(p);
}

inline int get_val(int p, int now){
	if(!p) return inf;
	if(a[a[p].l ].size >= now) return get_val(a[p].l , now);
	else if(now <= a[a[p].l ].size + a[p].cnt ) return a[p].val ;
	return get_val(a[p].r , now - a[a[p].l ].size - a[p].cnt );
}

//
inline int New1(int val){
	c[++tot1].val = val;
	c[tot1].dat = rand();
	c[tot1].cnt = c[tot1].size = 1;
	return tot1;
}

inline void update1(int p){
	c[p].size = c[c[p].l ].size + c[c[p].r ].size + c[p].cnt ;
}

inline void zig1(int &p){
	int q = c[p].l ;
	c[p].l = c[q].r;
	c[q].r = p;
	p = q;
	update1(c[p].r );
	update1(p);
}

inline void zag1(int &p){
	int q = c[p].r ;
	c[p].r = c[q].l ;
	c[q].l = p;
	p = q;
	update1(c[p].l );
	update1(p);
}

inline void insert1(int &p, int val){
	if(!p){
		p = New1(val);
		return ;
	}
	if(val == c[p].val ){
		c[p].cnt ++;
		update1(p);
		return ;
	}
	if(val < c[p].val ){
		insert1(c[p].l , val);
		if(c[p].dat < c[c[p].l ].dat ) zig1(p);
	}
	else {
		insert1(c[p].r , val);
		if(c[p].dat < c[c[p].r ].dat ) zag1(p);
	}
	update1(p);
}

inline int get_pre(int p, int val){
	int ans = 1;
	while(p){
		if(c[p].val == val){
			if(c[p].cnt > 1){
				ans = p;
				break;
			}
			if(c[p].l > 0){
				p = c[p].l ;
				while(c[p].r ) p = c[p].r ;
				ans = p;
			}
			break;
		}
		if(c[p].val < val && c[p].val > c[ans].val )
		ans = p;
		p = c[p].val < val ? c[p].r : c[p].l ;
	}
	return c[ans].val ;
}

inline int get_next(int p, int val){
	int ans = 2;
	while(p){
		if(c[p].val == val){
			if(c[p].cnt > 1){
				ans = p;
				break;
			}
			if(c[p].r > 0){
				p = c[p].r ;
				while(c[p].l ) p = c[p].l ;
				ans = p;
			}
			break;
		}
		if(c[p].val > val && c[p].val < c[ans].val ){
			ans = p;
		}
		p = c[p].val > val ? c[p].l : c[p].r ; 
	}
	return c[ans].val ;
}
//


int main(){
	New(-inf);
	New(inf);
	a[1].r = 2;
	update(root);
	New1(-inf);
	New1(inf);
	c[1].r = 2;
	update1(root1);
	srand(time(0));
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++)
	scanf("%d",&b[i].val );
	for(int i = 1; i <= n; i++)
	b[i].l = i - 1, b[i].r = i + 1;
	b[n].r = 0;
	for(int i = 1; i <= n; i++) la[i] = i;
	for(int i = 2; i <= n; i++){
		insert(root, abs(b[i].val - b[i - 1].val ));
	}
	for(int i = 1; i <= n; i++){
		insert1(root1, b[i].val );
		int x, y;
		x = abs(b[i].val - get_pre(root1, b[i].val ));
		y = abs(b[i].val - get_next(root1, b[i].val ));
		minn = min(min(minn, x), y);
	}
	for(int i = 1; i <= m; i++){
		scanf("%s",s);
		if(s[0] == 'I'){
			int x, y;
			scanf("%d%d",&x,&y);
			int u = la[x], now = i + n;
			if(b[i].r)
			remove(root, abs(b[u].val - b[b[u].r ].val ));
			b[now].l = u;
			b[now].r = b[u].r ;
			b[u].r = now;
			b[now].val = y;
			la[x] = now;
			insert(root, abs(b[now].val - b[b[now].l ].val ));
			insert(root, abs(b[now].val - b[b[now].r ].val ));
			insert1(root1, b[now].val );
			int xx, yy;
			xx = abs(b[now].val - get_pre(root1, b[now].val ));
			yy = abs(b[now].val - get_next(root1, b[now].val ));
			minn = min(min(minn, xx), yy);
		}
		else if(s[4] == 'G'){
			printf("%d\n",get_val(root, 2));
		}
		else {
			printf("%d\n",minn);
		}
	}
	
}

奉上又臭又长的代码