#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=500005;
int n,m,cnt1=0,cnt2=0,rt1=0,rt2=0,last[MAXN],lstcnt=0,minsortgap=numeric_limits<int>::max();
struct List{
    int l,r,x;
    List():l(0),r(0){}
}l[MAXN<<1|1];
inline void list_insert(int x,int p){
    l[++lstcnt].x=x;
    l[lstcnt].r=l[last[p]].r;
    l[lstcnt].l=last[p];
    l[l[last[p]].r].l=l[last[p]].r=lstcnt;
    last[p]=lstcnt;
}
mt19937 rnd(114514ull);
struct Treap{
    int x,l,r,p,sz;
}t1[MAXN<<1|1],t2[MAXN<<1|1];
inline void newnode1(int x){
    t1[++cnt1].x=x;
    t1[cnt1].p=rnd();
    t1[cnt1].sz=1;
    t1[cnt1].l=t1[cnt1].r=0;
}
inline void newnode2(int x){
    t2[++cnt2].x=x;
    t2[cnt2].p=rnd();
    t2[cnt2].sz=1;
    t2[cnt2].l=t2[cnt2].r=0;
}
inline void pushup1(int x){
    t1[x].sz=t1[t1[x].l].sz+t1[t1[x].r].sz+1;
}
inline void pushup2(int x){
    t2[x].sz=t2[t2[x].l].sz+t2[t2[x].r].sz+1;
}
void split1(int x,int w,int &l,int &r){
    if(!x)
        return (void)(l=r=0);
    if(t1[x].x<=w)
        l=x,split1(t1[x].r,w,t1[x].r,r);
    else
        r=x,split1(t1[x].l,w,l,t1[x].l);
    pushup1(x);
}
void split2(int x,int w,int &l,int &r){
    if(!x)
        return (void)(l=r=0);
    if(t1[x].x<=w)
        l=x,split2(t2[x].r,w,t2[x].r,r);
    else
        r=x,split2(t2[x].l,w,l,t2[x].l);
    pushup2(x);
}
int merge1(int l,int r){
    if(!l||!r)
        return l|r;
    if(t1[l].p>t1[r].p){
        t1[l].r=merge1(t1[l].r,r);
        pushup1(l);
        return l;
    }else{
        t1[r].l=merge1(l,t1[r].l);
        pushup1(r);
        return r;
    }
}
int merge2(int l,int r){
    if(!l||!r)
        return l|r;
    if(t2[l].p>t2[r].p){
        t2[l].r=merge1(t2[l].r,r);
        pushup2(l);
        return l;
    }else{
        t2[r].l=merge1(l,t2[r].l);
        pushup2(r);
        return r;
    }
}
int maxn(int x){
    while(t1[x].r)
        x=t1[x].r;
    return t1[x].x;
}
int minn(int x){
    while(t1[x].l)
        x=t1[x].l;
    return t1[x].x;
}
void insert1(int x){
    int l,r;
    split1(rt1,x,l,r);
    if(t1[l].sz)
        minsortgap=min(minsortgap,llabs(x-maxn(l)));
    if(t1[r].sz)
        minsortgap=min(minsortgap,llabs(x-minn(r)));
    newnode1(x);
    rt1=merge1(merge1(l,cnt1),r);
}
void insert2(int x){
    int l,r;
    split2(rt2,x,l,r);
    newnode2(x);
    rt2=merge2(merge2(l,cnt2),r);
}
void del(int x){
    int l,r,p;
    split2(rt2,x,l,r);
    split2(l,x-1,l,p);
    p=merge2(t2[p].l,t2[p].r);
    rt2=merge2(merge2(l,p),r);
}
int mingap(){
    int t=rt2;
    while(t2[t].l)
        t=t2[t].l;
    return t2[t].x; 
}
char s[15];
signed main(){
    // cin.tie(nullptr)->sync_with_stdio(false);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&l[++lstcnt].x);
        last[i]=i;
        l[i].l=i-1;l[i].r=i+1;
        insert1(l[i].x);
        if(i>1)
            insert2(llabs(l[i].x-l[i-1].x));
    }
    l[n].r=0;
    for(int i=1,x,k;i<=m;i++){
        scanf(" %s",s);
        if(s[0]=='I'){
            scanf("%lld%lld",&k,&x);
            if(k<n){
                del(llabs(l[last[k]].x-l[l[last[k]].r].x));
                insert2(llabs(x-l[l[last[k]].r].x));
            }
            // cerr<<"first if end\n";
            insert1(x);
            // cerr<<"insert1 end\n";
            insert2(llabs(x-l[last[k]].x));
            list_insert(x,k);
        }else if(s[4]=='G')
            printf("%lld\n",mingap());
        else
            printf("%lld\n",minsortgap);
    }
    return 0;
}