#include<bits/stdc++.h>
#define mxn 500005
using namespace std;
struct node{
	int ls, rs, vl, nc, siz;
	bool ct;//nc = nonce, 随机值 
}tr[mxn], tr2[mxn];
int cnt, ccnt, rt, rrt, ans = INT_MAX;
int nw(int x){
	tr[++cnt].vl = x;
	tr[cnt].nc = rand();
	tr[cnt].siz = 1;
	tr[cnt].ct = 1;
	return cnt;
}
void pup(int u){
	tr[u].siz = tr[tr[u].ls].siz + tr[tr[u].rs].siz + tr[u].ct;
}
int mg(int u, int v){
	if (!u || !v)
		return u | v;
	if (tr[u].nc < tr[v].nc){
		tr[u].rs = mg(tr[u].rs, v);
		pup(u);
		return u;
	}else{
		tr[v].ls = mg(u, tr[v].ls);
		pup(v);
		return v;
	}
}
void spt(int u, int x, int &a, int &b){
	if (!u){
		a = 0;
		b = 0;
	}else{
		if (tr[u].vl <= x){
			a = u;
			spt(tr[u].rs, x, tr[u].rs, b);
		}else{
			b = u;
			spt(tr[u].ls, x, a, tr[u].ls);
		}
		pup(u);
	}
}
int mx(int u){
	while (tr[u].ls)
		u = tr[u].ls;
	return tr[u].vl;
}
int mn(int u){
	while (tr[u].rs)
		u = tr[u].rs;
	return tr[u].vl;
}
void ins(int u){
	int ta, tb;
	spt(rt, u, ta, tb);
	int nnd = nw(u);
	rt = mg(mg(ta, nnd), tb);
}
int nww(int x){
	tr2[++ccnt].vl = x;
	tr2[ccnt].nc = rand();
	tr2[ccnt].siz = 1;
	tr2[ccnt].ct = 1;
	return ccnt;
}
void pupp(int u){
	tr2[u].siz = tr2[tr2[u].ls].siz + tr2[tr2[u].rs].siz + tr2[u].ct;
}
void sptt(int u, int x, int &a, int &b){
	if (!u){
		a = 0;
		b = 0;
	}else{
		if (tr2[u].vl <= x){
			a = u;
			sptt(tr2[u].rs, x, tr2[u].rs, b);
		}else{
			b = u;
			sptt(tr2[u].ls, x, a, tr2[u].ls);
		}
		pupp(u);
	}
}
int mgg(int u, int v){
	if (!u || !v)
		return u | v;
	if (tr2[u].nc < tr2[v].nc){
		tr2[u].rs = mg(tr2[u].rs, v);
		pupp(u);
		return u;
	}else{
		tr2[v].ls = mg(u, tr2[v].ls);
		pupp(v);
		return v;
	}
}
void iins(int u){
	int ta, tb;
	sptt(rrt, u, ta, tb);
	if (tr2[ta].siz)
		ans = min(ans, abs(u - mx(ta)));
	if (tr2[tb].siz)
		ans = min(ans, abs(u - mn(tb)));
	int nnd = nww(u);
	rrt = mgg(mgg(ta, nnd), tb);
}
void del(int u){
	int ta, tb, tc;
	spt(rrt, u, ta, tc);
	spt(ta, u - 1, ta, tb);
	tb = mg(tr[tb].ls, tr[tb].rs);
	rrt = mg(mg(ta, tb), tc);
}
int n, m, a[mxn], b[mxn];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		b[i] = a[i];
	}
	for (int i = 1; i < n; i++)
		ins(abs(a[i + 1]) - a[i]);
	for (int i = 1; i <= n; i++)
		iins(a[i]);
	while (m--){
		string op;
		cin >> op;
		if (op == "INSERT"){
			int u, v;
			cin >> u >> v;
			iins(v);
			if (u != n){
				del(abs(a[u + 1] - b[u]));
				ins(abs(a[u + 1]) - v);
			}
			ins(abs(b[u] - v));
			b[u] = v;
		}else if (op == "MIN_GAP")
			cout << mn(rt) << "\n";
		else
			cout << ans << "\n";
	}
}