#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
#define fore(i,now) for(reg int i=head[now];i;i=e[i].nxt)
#define fora(i,a,b,c) for(reg int i=a;i<=b;i+=c)
#define forb(i,a,b,c) for(reg int i=a;i>=b;i-=c)
#define uLL unsigned LL
#define INF 0x3f3f3f3f
#define LL long long
#define reg register
#define N 500005
#define R read()
inline LL read(){
    LL s=0, f=1; char c=getchar();
    while(c<'0'||c>'9') { if(c=='-') f=-f; c=getchar(); }
    while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^48), c=getchar();
    return s*f;
}
inline string getStr(){
    char c=getchar(); string s("");
    while(c==' '||c=='\n'||c=='\r') c=getchar();
    while(c!=' '&&c!='\n'&&c!='\r') s+=c, c=getchar();
    return s;
}
const double alpha=0.75;
struct ScapegoatTree {
    struct Node {
        Node *l, *r;
        int val, siz, num, fact;
    } *rot, *null;
    int cnt;
    ScapegoatTree() { cnt=0; rot=null=new Node; }
    inline int Imbalance(Node* &x){
        return x->num&&(
            (double)max(x->l->siz, x->r->siz)>alpha*(double)x->siz||
            (double)x->fact<alpha*(double)x->siz
        );
    }
    inline void Update(Node* &x){
        x->siz=x->l->siz+x->num+x->r->siz;
        x->fact=x->l->fact+x->num+x->r->fact;
    }
    void Unfold(Node* &x, vector<Node*> &v){
        if(x==null) return ;
        Unfold(x->l, v);
        if(x->num) v.push_back(x);
        Unfold(x->r, v);
        if(!(x->num)) delete x;
    }
    Node* Rebuild(vector<Node*> &v, int l, int r){
        if(l>=r) return null;
        int mid=(l+r)>>1;
        Node* x=v[mid];
        x->l=Rebuild(v, l, mid);
        x->r=Rebuild(v, mid+1, r);
        Update(x);
        return x;
    }
    inline void Counterbalance(Node* &x){
        vector<Node*> v;
        Unfold(x, v);
        x=Rebuild(v, 0, v.size());
    }
    void Insert(Node* &x, int val){
        if(x==null){
            ++cnt;
            x=new Node;
            x->val=val;
            x->l=x->r=null;
            x->num=x->siz=x->fact=1;
            return ;
        }
        ++(x->siz), ++(x->fact);
        if(val==x->val) ++(x->num), ++cnt;
        if(val<x->val) Insert(x->l, val);
        if(val>x->val) Insert(x->r, val);
        if(Imbalance(x)) Counterbalance(x);
    }
    void Erase(Node* &x, int val){
        if(val==x->val&&x->num){
            --cnt, --(x->num), --(x->fact);
            return ;
        }
        --(x->fact);
        if(val<x->val) Erase(x->l, val);
        if(val>x->val) Erase(x->r, val);
    }
    int SreachK(Node* &x, int k){
        if(x->l->fact<k&&k<=x->l->fact+x->num)
            return x->val;
        if(k<=x->l->fact) return SreachK(x->l, k);
        return SreachK(x->r, k-(x->l->fact)-(x->num));
    }
    int Rank(Node* &x, int val){
        if(x==null) return 1;
        if(val<=x->val) return Rank(x->l, val);
        return x->l->fact+x->num+Rank(x->r, val);
    }
    int Find(Node* &x, int val){
        if(x==null) return 0;
        if(val==x->val) return x->num;
        if(val<x->val) return Find(x->l, val);
        if(val>x->val) return Find(x->r, val);
    }
    int Prec(int val){
        if(!cnt) return INF;
        if(Find(rot, val)>1) return val;
        int f=Rank(rot, val)-1;
        if(f<=0) return INF;
        return SreachK(rot, f);
    }
    int Succ(int val){
        if(!cnt) return INF;
        if(Find(rot, val)>1) return val;
        int f=Rank(rot, val+1);
        if(f>=cnt+1) return INF;
        return SreachK(rot, f);
    }
} mg, msg;
int n, m, mgAns, msgAns, a[N];
vector<int> v[N];
int main(){
    mgAns=msgAns=INF/10;
    n=R, m=R;
    fora(i, 1, n, 1){
        a[i]=R; v[i].push_back(a[i]);
        msg.Insert(msg.rot, a[i]);
        if(i>1)
            mg.Insert(mg.rot, abs(a[i]-a[i-1]));
    }
    sort(a+1, a+n+1);
    fora(i, 2, n, 1)
        msgAns=min(msgAns, a[i]-a[i-1]);
    while(m--){ 
        string op=getStr();
        if(op[4]=='R'){
            int x=R, y=R;
            msg.Insert(msg.rot, y);
            int a=msg.Prec(y), b=msg.Succ(y);
            msgAns=min(msgAns, min(abs(a-y), abs(b-y)));
            mgAns=min(mgAns, abs(v[x][v[x].size()-1]-y));
            if(x<n){
                mg.Insert(mg.rot, abs(v[x+1][0]-y));
                mg.Erase(mg.rot, abs(v[x+1][0]-v[x][v[x].size()-1]));
            }
            v[x].push_back(y);
        }
        else if(op[4]=='G') printf("%d\n", min(mgAns, mg.SreachK(mg.rot, 1)));
        else if(op[4]=='S') printf("%d\n", msgAns);
    }
    return 0;
}