#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,a[N],x,y,mi=1e9,e,b=1e9,z[2*N],v,ans[N],ss;
vector<int> p[N];
string s;
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
	    cin>>a[i];
	    p[i].push_back(a[i]);
	    for(int j=1;j<=v;j++)
			b=min(b,abs(a[i]-z[j]));
	    v+=1;
	    z[v]=a[i];
	}
	for(int i=1;i<n;i++)
	    mi=min(mi,abs(a[i]-a[i+1]));
	for(int i=1;i<=m;i++){
		cin>>s;
		if(s=="INSERT"){
			cin>>x>>y;
			p[x].push_back(y);
			mi=min(mi,abs(y-p[x][p[x].size()-2]));
		   	v+=1;
			z[v]=y;
		}
		if(s=="MIN_GAP"){
			e=1e9;
			for(int j=2;j<=n;j++)
			    e=min(e,abs(a[j]-p[j-1][p[j-1].size()-1]));
			ans[++ss]=min(e,mi);
		}
		if(s=="MIN_SORT_GAP"){
			sort(z+1,z+v+1);
			b=1e9;
			for(int j=1;j<=v-1;j++)
			    b=min(b,z[j+1]-z[j]);
		    ans[++ss]=b;
		}
	}
	for(int i=1;i<=ss;i++)
	    cout<<ans[i]<<endl;
	return 0;
}