#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,a[N],na[N],ed[N];
string opt;
int loc,x;
int lst,nxt,ans=INT_MAX;
multiset<int>nums;
multiset<int>chas;
multiset<int>::iterator it;
inline void init()
{
	for(int i=0;i<N;i++)
		a[i]=ed[i]=-1;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		na[i]=a[i];
		nums.insert(a[i]);
		if(i!=1)
			chas.insert(abs(a[i]-a[i-1]));
	}
	sort(na+1,na+n+1);
	for(int i=2;i<=n;i++)
		ans=min(ans,na[i]-na[i-1]);
	for(int i=1;i<=m;i++)
	{
		cin>>opt;
		if(opt=="INSERT")
		{
			cin>>loc>>x;
			if(ed[loc]!=-1&&loc!=n)
				chas.erase(chas.find(abs(a[loc+1]-ed[loc])));
			if(ed[loc]==-1&&loc!=n)
				chas.erase(chas.find(abs(a[loc+1]-a[loc])));
			it=nums.upper_bound(x);
			if(it!=nums.end())
				lst=*(--it),ans=min(ans,x-lst);
			it=nums.lower_bound(x);
			if(it!=nums.end())
				nxt=*it,ans=min(ans,nxt-x);
			nums.insert(x);
			if(ed[loc]!=-1)
				chas.insert(abs(x-ed[loc]));
			else
				chas.insert(abs(x-a[loc]));
			if(loc!=n)
				chas.insert(abs(x-a[loc+1]));
			ed[loc]=x;
		}
		else if(opt=="MIN_GAP")
			cout<<*chas.begin()<<'\n';
		else
			cout<<ans<<'\n';
	}
	return 0;
}