#include <bits/stdc++.h>

using namespace std;

#define INF 99999999999LL

#define maxn 2000000

#define int long long

int n, m, tot, M1 = INF, M2 = INF, a[maxn];

int b[maxn], root;

struct tree

{

    int l, r, num;

}T[maxn];

struct node

{

    int v, ch[], fa;

}P[maxn];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

struct Splay_Balanced_Tree

{

    void rotate(int x)

    {

        int f = P[x].fa, gf = P[f].fa;

        int k = x == P[f].ch[];

        P[x].fa = gf;

        if(gf) P[gf].ch[f == P[gf].ch[]] = x;

        P[f].ch[k] = P[x].ch[k ^ ], P[P[x].ch[k ^ ]].fa = f;

        P[f].fa = x, P[x].ch[k ^ ] = f;

    }

    void Splay(int x, int goal)

    {

        while(P[x].fa != goal)

        {

            int f = P[x].fa, gf = P[f].fa;

            if(gf != goal) (P[f].ch[] == x) ^ (P[gf].ch[] == f) ? rotate(x) : rotate(f);

            rotate(x);

        }

        if(goal == ) root = x;

    }

    void ins(int x)

    {

        int u = root, ff = ;

        while(u && P[u].v != x)

        {

            ff = u;

            u = P[u].ch[P[u].v < x];

        }

        if(!u)

        {

            u = ++ tot;

            P[u].fa = ff;

            if(ff) P[ff].ch[P[ff].v < x] = u;

            P[u].v = x;

            Splay(u, );

        }

    }

    void Find(int x)

    {

        int u = root;

        if(!u) return;

        while(P[u].v != x && P[u].ch[P[u].v < x]) u = P[u].ch[P[u].v < x];

        Splay(u, );

    }

    int next(int x, int k)

    {

        Find(x);

        int u = root;

        if(P[u].v == x) return P[u].v;

        if((P[u].v < x && !k) || (P[u].v > x && k)) return P[u].v;

        u = P[u].ch[k];

        while(P[u].ch[k ^ ]) u = P[u].ch[k ^ ];

        return P[u].v;

    }

}SBT;

struct Segament_Tree

{

    void build(int p, int l, int r)

    {

        T[p].l = l, T[p].r = r;

        if(l == r)

        {

            T[p].num = abs(a[l] - a[l - ]);

            return;

        }

        int mid = (l + r) >> ;

        build(p << , l, mid), build(p <<  | , mid + , r);

        T[p].num = min(T[p << ].num, T[p <<  | ].num);

    }

    void update(int p, int x, int num)

    {

        int mid = (T[p].l + T[p].r) >> ;

        if(T[p].l == T[p].r)

        {

            T[p].num = num;

            return;

        }

        if(x <= mid) update(p << , x, num);

        else update(p <<  | , x, num);

        T[p].num = min(T[p << ].num, T[p <<  | ].num);

    }

}SGT;

signed main()

{

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

    SBT.ins(INF), SBT.ins(- INF);

    a[] = a[n + ] = INF;

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

    {

        a[i] = read();

        if(i != )

        {

            int l = SBT.next(a[i], ), r = SBT.next(a[i], );

            M2 = min(M2, min(abs(l - a[i]), abs(r - a[i])));

        }

        SBT.ins(a[i]);

        b[i] = a[i];

    }

    SGT.build(, , n);

    for(int i = ; i <= m; i ++)

    {

        string s;

        cin >> s;

        if(s[] == 'I')

        {

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

            int l = SBT.next(y, ), r = SBT.next(y, );

            M2 = min(M2, min(abs(l - y), abs(r - y)));

            SBT.ins(y);

            M1 = min(M1, abs(b[x] - y));

            SGT.update(, x + , abs(a[x + ] - y));

            b[x] = y;

        }

        else if(s[] == 'G') printf("%lld\n", min(M1, T[].num));

        else printf("%lld\n", M2);

    }

    return ;

}