#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
int a[1145141],b[1145141],lsta[1145141],lstb[1145141];
int rt1,rt2,l1=0,r1=0,l2=0,r2=0,px1,px2,cnt1=0,cnt2=0;
struct node{
	int l,r,siz,val,randval;
}Treap1[1145141],Treap2[1145141];
void pushup1(int p){
	Treap1[p].siz=Treap1[Treap1[p].l].siz+Treap1[Treap1[p].r].siz+1;
	return ;
}
void build1(int x){
	++cnt1;
	Treap1[cnt1].l=Treap1[cnt1].r=0;
	Treap1[cnt1].siz=1;
	Treap1[cnt1].val=x;
	Treap1[cnt1].randval=rand();
	return ;
}
void Split1(int p,int val,int &l,int &r){
	if(!p){
		l=r=0;
		return ;
	}
	if(Treap1[p].val<=val){ 
		l=p; 
		Split1(Treap1[p].r,val,Treap1[p].r,r); 
	}else{
		r=p; 
		Split1(Treap1[p].l,val,l,Treap1[p].l); 
	}
	pushup1(p);
	return ;
}

int Merge1(int l,int r){
	if(!l||!r) return l+r;
	if(Treap1[l].randval<=Treap1[r].randval){
		Treap1[l].r=Merge1(Treap1[l].r,r);
		pushup1(l);
		return l;
	}
	Treap1[r].l=Merge1(l,Treap1[r].l);
	pushup1(r);
	return r;
}

void Insert1(int x){
	Split1(rt1,x,l1,r1);
	build1(x);
	rt1=Merge1(Merge1(l1,cnt1),r1);
	return ;
}

void Delete1(int x){
	Split1(rt1,x,l1,r1);
	Split1(l1,x-1,l1,px1);
	px1=Merge1(Treap1[px1].l,Treap1[px1].r);
	rt1=Merge1(Merge1(l1,px1),r1);
	return ;
}

int rk1(int p,int k){
	if(k==Treap1[Treap1[p].l].siz+1) return p;
	if(k<Treap1[Treap1[p].l].siz+1) return rk1(Treap1[p].l,k);
	k-=Treap1[Treap1[p].l].siz+1;
	return rk1(Treap1[p].r,k);
}
void pushup2(int p){
	Treap2[p].siz=Treap2[Treap2[p].l].siz+Treap2[Treap2[p].r].siz+1;
	return ;
}
void build2(int x){
	++cnt2;
	Treap2[cnt2].l=Treap2[cnt2].r=0;
	Treap2[cnt2].siz=1;
	Treap2[cnt2].val=x;
	Treap2[cnt2].randval=rand();
	return ;
}
void Split2(int p,int val,int &l,int &r){
	if(!p){
		l=r=0;
		return ;
	}
	if(Treap2[p].val<=val){ 
		l=p; 
		Split2(Treap2[p].r,val,Treap2[p].r,r); 
	}else{
		r=p; 
		Split2(Treap2[p].l,val,l,Treap2[p].l); 
	}
	pushup2(p);
	return ;
}

int Merge2(int l,int r){
	if(!l||!r) return l+r;
	if(Treap2[l].randval<=Treap2[r].randval){
		Treap2[l].r=Merge2(Treap2[l].r,r);
		pushup2(l);
		return l;
	}
	Treap2[r].l=Merge2(l,Treap2[r].l);
	pushup2(r);
	return r;
}

void Insert2(int x){
	Split2(rt2,x,l2,r2);
	build2(x);
	rt2=Merge2(Merge2(l2,cnt2),r2);
	return ;
}

void Delete2(int x){
	Split2(rt2,x,l2,r2);
	Split2(l2,x-1,l2,px2);
	px2=Merge2(Treap2[px2].l,Treap2[px2].r);
	rt2=Merge2(Merge2(l2,px2),r2);
	return ;
}

int rk2(int p,int k){
	if(k==Treap2[Treap2[p].l].siz+1) return p;
	if(k<Treap2[Treap2[p].l].siz+1) return rk2(Treap2[p].l,k);
	k-=Treap2[Treap2[p].l].siz+1;
	return rk2(Treap2[p].r,k);
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) b[i]=a[i];
	for(int i=1;i<n;i++) Insert1(abs(a[i+1]-a[i]));
	sort(b+1,b+n+1);
	for(int i=1;i<n;i++) Insert2(abs(b[i+1]-b[i]));
	for(int i=1;i<=n;i++) lsta[i]=a[i];
	for(int i=1;i<=n;i++) lstb[i]=b[i];
	while(q--){
		string op;
		cin>>op;
		if(op=="INSERT"){
			int ii,x;
			cin>>ii>>x;
			if(ii==n){
				Delete1(abs(a[n]-lsta[n]));
				Insert1(abs(x-lsta[n]));
				Delete2(abs(b[n]-lstb[n]));
				Insert2(abs(x-lstb[n]));
				lsta[n]=x; lstb[n]=x;
			}
			else{
				Delete1(abs(a[ii+1]-lsta[ii]));
				Insert1(abs(x-lsta[ii]));
				Insert1(abs(a[ii+1]-x));
				Delete2(abs(b[ii+1]-lstb[ii]));
				Insert2(abs(x-lstb[ii]));
				Insert2(abs(b[ii+1]-x));
				lsta[ii]=x; lstb[ii]=x;
			}
		}
		else if(op=="MIN_GAP") cout<<Treap1[rk1(rt1,1)].val<<endl;
		else cout<<Treap2[rk2(rt2,1)].val<<endl;
	}
	return 0;
}