#include #include #include #include #include #include #include #include #include #include
using namespace std;
const int N = 1000005; const int inf = 0X7fffffff; const int mod = 1000000;
struct cmp { bool operator()(int &a, int &b) const { return a > b; } };
struct tree { int l, r; int fa, k; int s; } t[N];
int n, m; int delta, ans; int root = 0, tot; long long num = 0;
int read() { int x = 0, v = 1; char ch = getchar(); for (; ch < '0' || ch > '9'; v = (ch == '-') ? (-1) : (v), ch = getchar()) ; for (; ch <= '9' && ch >= '0'; x = x * 10 + ch - '0', ch = getchar()) ; return x * v; }
void clean(int x) { t[x].l = t[x].r = t[x].fa = t[x].k = t[x].s = 0; }
void rttl(int x) { int y = t[x].r; if (x == root) root = y; t[x].r = t[y].l; t[t[y].l].fa = x; t[y].l = x; t[y].fa = t[x].fa; if (x == t[t[x].fa].l) t[t[x].fa].l = y; else t[t[x].fa].r = y; t[x].fa = y; t[x].s = t[t[x].l].s + t[t[x].r].s + 1; t[y].s = t[t[y].l].s + t[t[y].r].s + 1; }
void rttr(int x) { int y = t[x].l; if (x == root) root = y; t[x].l = t[y].r; t[t[y].r].fa = x; t[y].r = x; t[y].fa = t[x].fa; if (x == t[t[x].fa].l) t[t[x].fa].l = y; else t[t[x].fa].r = y; t[x].fa = y; t[x].s = t[t[x].l].s + t[t[x].r].s + 1; t[y].s = t[t[y].l].s + t[t[y].r].s + 1; }
int ans_sort = inf;
void splay(int x, int flag) { if (x == 0) return; while (x != root) { int f = t[x].fa; if (f == x) return; if ((flag) && (f == root)) return; if ((flag) && (t[f].fa == root)) { if (x == t[f].l) rttr(f); else rttl(f); return; } if (f == root) if (x == t[f].l) rttr(f); else rttl(f); else { int p = t[f].fa; if (x == t[f].l) { if (f == t[p].l) { rttr(p); rttr(f); } else { rttr(f); rttl(p); } } else { if (f == t[p].l) { rttl(f); rttr(p); } else { rttl(p); rttl(f); } } } } }
void insert(int k) { if (!root) { root = ++tot; t[tot].s = 1; t[tot].k = k; return; } int x = root, y; while (x) { y = x; t[x].s++; if ((abs(k - t[x].k) < ans_sort)) ans_sort = abs(k - t[x].k); if ((x == t[x].l) || (x == t[x].r)) break; if (k < t[x].k) x = t[x].l; else x = t[x].r; } t[++tot].s = 1; t[tot].k = k; t[tot].fa = y; if (k < t[y].k) t[y].l = tot; else t[y].r = tot; splay(tot, 0); }
int ls[N][3];
std::priority_queue<int, std::vector, cmp> del; std::priority_queue<int, std::vector, cmp> ins;
int main() { scanf("%d%d", &n, &m); root = 0; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); ls[i][1] = x; ls[i][2] = x; insert(ls[i][1]); if (i != 1) { ins.push(abs(ls[i][1] - ls[i - 1][2])); } } for (int i = 1; i <= m; i++) { string s; cin >> s; if (s[0] == 'I') { int x, y; scanf("%d%d", &x, &y); insert(y); if (x != n) { del.push(abs(ls[x + 1][1] - ls[x][2])); ins.push(abs(ls[x + 1][1] - y)); } ins.push(abs(ls[x][2] - y)); ls[x][2] = y; } else if (s.length() > 10) printf("%d\n", ans_sort); else { while (del.top() == ins.top()) { del.pop(), ins.pop(); } printf("%d\n", ins.top()); } } }