#include<cmath>

 #include<set>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #define ite multiset<int>::iterator

 using namespace std;

 typedef long long ll;

 const int N = 3e6+;

 multiset<int> sorted,listed;

 int n,m,tomin;

 int last[N],front[N];

 ll read() {

     char c=getchar();

     ll f=,x=;

     while(!isdigit(c)) {

         if(c=='-') f=-; c=getchar();

     }

     while(isdigit(c))

         x=x*+c-'',c=getchar();

     return x*f;

 }

 int abs(int x) { return x<? -x:x; }

 int main()

 {

     n=read(); m=read();

     tomin=1e9;

     for(int i=;i<=n;i++) {

         front[i]=read();

         last[i]=front[i];

         sorted.insert(front[i]);

         if(i!=) listed.insert(abs(front[i]-front[i-]));

     }

     ite l;

     for(ite r=sorted.begin();r!=sorted.end();r++) {

         if(r!=sorted.begin())

             tomin=min(tomin,abs(*r-*l));

         l=r;

     }

     char op[]; int x,y;

     while(m--) {

         scanf("%s",op);

         if(op[]=='I') {

             x=read(),y=read();

             ite it=sorted.insert(y);

             if(it!=sorted.begin())

                 --it , tomin=min(tomin,abs(y-*it)) , ++it;

             if(it!=sorted.end())

                 ++it , tomin=min(tomin,abs(*it-y)) , --it;

             it=listed.find(abs(front[x+]-last[x]));

             listed.erase(it);

             listed.insert(abs(y-front[x+]));

             listed.insert(abs(y-last[x]));

             last[x]=y;

         } else

         if(strlen(op)==) {

             printf("%d\n",*listed.begin());

         } else {

             printf("%d\n",tomin);

         }

     }

     return ;

 }