#include <set>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define maxn 1000005class HeadType {    private:        int head[maxn*2],cnt;            public:        bool size()        {            return cnt;        }                int top()        {            if(!cnt) return 0x7fffffff;            return head[1];        }                inline void push(int x)        {            head[++cnt]=x;            int now=cnt,tmp;            while(now>1)            {                if(head[now>>1]>head[now]) tmp=head[now],head[now]=head[now>>1],now>>=1,head[now]=tmp;                else break;            }        }                inline void pop()        {            head[1]=head[cnt--];            if(cnt==0) return ;            int pos,pos_,now=1;            while(1)            {                pos=now,pos_=head[now];                if((now<<1)<=cnt&&head[now<<1]<head[pos]) pos=now<<1,pos_=head[now<<1];                if((now<<1|1)<=cnt&&head[now<<1|1]<head[pos]) pos=now<<1|1,pos_=head[now<<1|1];                if(pos==now) return ;                head[pos]=head[now],head[now]=pos_,now=pos;            }        }};class HeadType ai,bi,ci;struct ListType {    int pre,dis;};struct ListType bili[maxn];int n,m,vi[maxn],tot;set<int>so;inline void in(int &now){    int if_z=1;now=0;    char Cget=getchar();    while(Cget>‘9‘||Cget<‘0‘)    {        if(Cget==‘-‘) if_z=-1;        Cget=getchar();    }    while(Cget>=‘0‘&&Cget<=‘9‘)    {        now=now*10+Cget-‘0‘;        Cget=getchar();    }    now*=if_z;}int main(){    in(n),in(m);bili[0].dis=1e9,bili[n+1].dis=1e9,tot=n+1;    for(int i=1;i<=n;i++)    {        bili[i].pre=i-1,in(bili[i].dis);        ai.push(abs(bili[i].dis-bili[i-1].dis));        so.insert(bili[i].dis),vi[i]=bili[i].dis;    }    sort(vi+1,vi+n+1),bili[n+1].pre=n,ai.push(abs(bili[n+1].dis-bili[bili[n+1].pre].dis));    for(int i=2;i<=n;i++) ci.push(abs(vi[i]-vi[i-1]));    char op[15];int p,x;    for(;m--;)    {        scanf("%s",op);        if(op[0]==‘I‘)        {            in(p),in(x);p++;            bi.push(abs(bili[p].dis-bili[bili[p].pre].dis));            ai.push(abs(x-bili[bili[p].pre].dis)),ai.push(abs(bili[p].dis-x));            bili[++tot].pre=bili[p].pre,bili[tot].dis=x,bili[p].pre=tot;            set<int>::iterator it=so.lower_bound(x);            if(it!=so.end()) ci.push(abs(*it-x));            if(it!=so.begin()) it--,ci.push(abs(*it-x));            so.insert(x);        }        else if(op[4]==‘S‘) printf("%d\n",ci.top());        else        {            while(ai.top()==bi.top()) ai.pop(),bi.pop();            printf("%d\n",ai.top());        }    }    return 0;}

#pragma GCC optimize("O2")#include <cstdio>#include <iostream>#include <algorithm> using namespace std; #define maxn 1000005#define INF 0x7fffffff class SplayTreeType {    private:        int ch[maxn][2],key[maxn],minkey[maxn],size[maxn];        int pre[maxn],f[maxn];             public:        int ai[maxn],tot,root,n;                 inline void updata(int now)        {            size[now]=1,minkey[now]=abs(key[now]-pre[now]);            if(ch[now][0]) size[now]+=size[ch[now][0]],minkey[now]=min(minkey[now],minkey[ch[now][0]]);            if(ch[now][1]) size[now]+=size[ch[now][1]],minkey[now]=min(minkey[now],minkey[ch[now][1]]);        }                 inline int tree_build(int l,int r,int fa)        {            int now=l+r>>1;            key[now]=ai[now],pre[now]=ai[now-1],f[now]=fa;            minkey[now]=abs(key[now]-pre[now]);            if(now>l) ch[now][0]=tree_build(l,now-1,now);            if(now<r) ch[now][1]=tree_build(now+1,r,now);            updata(now);return now;        }                 inline void rotate(int now,int &to)        {            int fa=f[now],ffa=f[fa];bool pos=(ch[f[now]][1]==now);            if(fa==to) to=now;            else if(ffa) ch[ffa][ch[f[fa]][1]==fa]=now;            ch[fa][pos]=ch[now][pos^1];            if(ch[fa][pos]) f[ch[fa][pos]]=fa;            ch[now][pos^1]=fa,f[fa]=now,f[now]=ffa;            updata(fa);        }                 inline void splay(int now,int &to)        {            while(now!=to)            {                int fa=f[now],ffa=f[fa];                if(fa!=to) rotate((ch[f[now]][1]==now)==(ch[f[fa]][1]==fa)?fa:now,to);                rotate(now,to);            }            updata(now);        }                 inline void insert(int p,int ci)        {            splay(p+2,root),pree();            ch[ch[root][0]][1]=++tot;            f[tot]=ch[root][0],key[tot]=ci,pre[tot]=key[ch[root][0]];            pre[root]=key[tot],updata(tot),updata(ch[root][0]),updata(root);        }                 inline void pree()        {            int now=ch[root][0];            while(ch[now][1]) now=ch[now][1];            splay(now,ch[root][0]);        }                 inline void suff()        {            int now=ch[root][1];            while(ch[now][0]) now=ch[now][0];            splay(now,ch[root][1]);        }                 inline void insert_(int ci)        {            int now=root,fa=0;            while(1)            {                fa=now;                if(key[now]<=ci) now=ch[now][1];                else now=ch[now][0];                if(now==0)                {                    now=++tot;                    ch[fa][ci>key[fa]]=now;                    f[now]=fa,key[now]=ci,size[now]=1;                    splay(now,root),pree(),suff();                    pre[root]=key[ch[root][0]],pre[ch[root][1]]=key[root];                    updata(ch[root][0]),updata(ch[root][1]),updata(root);return ;                }            }        }                 inline int query()        {            splay(2,root),splay(n+2,ch[root][1]);            return minkey[ch[ch[root][1]][0]];        }};struct SplayTreeType ai,bi; int n,m; inline void in(int &now){    int if_z=1;now=0;    char Cget=getchar();    while(Cget>‘9‘||Cget<‘0‘)    {        if(Cget==‘-‘) if_z=-1;        Cget=getchar();    }    while(Cget>=‘0‘&&Cget<=‘9‘)    {        now=now*10+Cget-‘0‘;        Cget=getchar();    }    now*=if_z;} int main(){    in(n),in(m);ai.tot=n+2,bi.tot=n+2,ai.n=n,bi.n=n;    for(int i=2;i<=n+1;i++) in(ai.ai[i]),bi.ai[i]=ai.ai[i];char op[15];int u,v,x;    sort(bi.ai+2,bi.ai+n+2);bi.ai[1]=-(INF-1),bi.ai[bi.tot]=INF;    ai.root=ai.tree_build(1,n+2,0),bi.root=bi.tree_build(1,n+2,0);    for(;m--;)    {        scanf("%s",op);        if(op[0]==‘I‘) in(u),in(v),ai.insert(u,v),bi.insert_(v);        else if(op[0]==‘M‘)        {            if(op[4]==‘S‘) printf("%d\n",bi.query());            else printf("%d\n",ai.query());        }    }    return 0;}