考虑操作 1，显然和 vector 很像，所以直接用 vector 模拟。
再看操作 2，要看相邻的差值最小值，发现在操作 1 的过程中相当于删除当前队尾和下一个队首，并加入新的两个贡献，因此要支持插入删除求最小值。
最后是操作 3，显然是要支持插入、前驱后继（求出差值最小值）。

然后我们发现，操作 1 显然很好维护，操作 2、3 可以直接用平衡树处理。
什么平衡树呢？只要能过板子的平衡树就行了（）（）

于是我使用 Treap，在洛谷跑的飞快，在 AcWing 需要手动卡常或吸氧。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 15;
const int INF = 0x3f3f3f3f;
int n, m;
vector<int> a[N];

struct Treap {
    struct Tree {
        int ls, rs;
        int val, prio;
        int cnt, sz;
    } tr[N];
    int tot, rt;

    int get_node(int val) {
        tr[++tot].val = val;
        tr[tot].prio = rand();
        tr[tot].cnt = tr[tot].sz = 1;
        return tot;
    }

    void pushup(int u) {
        tr[u].sz = tr[tr[u].ls].sz + tr[tr[u].rs].sz + tr[u].cnt;
    }

    void zag(int &x) {
        int y = tr[x].rs;
        tr[x].rs = tr[y].ls, tr[y].ls = x, x = y;
        pushup(tr[x].ls), pushup(x);
    }

    void zig(int &x) {
        int y = tr[x].ls;
        tr[x].ls = tr[y].rs, tr[y].rs = x, x = y;
        pushup(tr[x].rs), pushup(x);
    }

    void build() {
        tot = 0;
        get_node(-INF); get_node(INF);
        rt = 1, tr[1].rs = 2;
        if (tr[2].prio > tr[1].prio) zag(rt);
    }

    void insert(int &u, int val) {
        if (!u) u = get_node(val);
        else if (val == tr[u].val) tr[u].cnt++;
        else {
            if (val < tr[u].val) {
                insert(tr[u].ls, val);
                if (tr[tr[u].ls].prio > tr[u].prio) zig(u);
            } else {
                insert(tr[u].rs, val);
                if (tr[tr[u].rs].prio > tr[u].prio) zag(u);
            }
        }
        pushup(u);
    }

    void remove(int &u, int val) {
        if (!u) return;
        if (val == tr[u].val) {
            if (tr[u].cnt > 1) tr[u].cnt--;
            else if (!tr[u].ls && !tr[u].rs) u = 0;
            else if (!tr[u].rs || tr[tr[u].ls].prio > tr[tr[u].rs].prio) {
                zig(u);
                remove(tr[u].rs, val);
            } else {
                zag(u);
                remove(tr[u].ls, val);
            }
        } else {
            if (val < tr[u].val) remove(tr[u].ls, val);
            else remove(tr[u].rs, val);
        }
        pushup(u);
    }

    int pre(int u, int val) {
        if (!u) return -INF;
        if (val == tr[u].val) return val;
        if (val < tr[u].val) return pre(tr[u].ls, val);
        return max(tr[u].val, pre(tr[u].rs, val));
    }

    int nxt(int u, int val) {
        if (!u) return INF;
        if (val == tr[u].val) return val;
        if (val > tr[u].val) return nxt(tr[u].rs, val);
        return min(tr[u].val, nxt(tr[u].ls, val));
    }

    int get_Min() {
        int Min = 0x3f3f3f3f;
        int u = rt;
        while (u) {
            if (tr[u].val != -INF) Min = min(Min, tr[u].val);
            if (tr[u].ls) u = tr[u].ls;
            else u = tr[u].rs;
        }
        return Min;
    }

    void debug() {
        // cout << '\t' << rt << endl;
        // for (int u = 1; u <= tot; u++) {
        //     cout << '\t' << u << ' ' << tr[u].val << ' ' << tr[u].cnt << ' ' << tr[u].sz << ' ' << tr[u].ls << ' ' << tr[u].rs << endl;
        // } puts("");
    }

} t1, t2;

int ans = 0;

int main() {
    srand(time(0));
    cin >> n >> m; ans = 0x3f3f3f3f;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        a[i].push_back(x);
    }
    t1.build(), t2.build();
    t1.debug();

    for (int i = 1; i <= n; i++) {
        if (i < n) t1.insert(t1.rt, abs(*(a[i].end() - 1) - *(a[i + 1].begin()) )), t1.debug();
        int val = a[i][0];

        ans = min(ans, val - t2.pre(t2.rt, val));
        ans = min(ans, t2.nxt(t2.rt, val) - val);
        // cout << '\t' << val << ' ' << t2.pre(t2.rt, val) << ' ' << t2.nxt(t2.rt, val) << endl;
        t2.insert(t2.rt, a[i][0]);
    }

    while (m--) {
        string opt; cin >> opt;
        if (opt == "INSERT") {
            int x, val; cin >> x >> val;
            t1.remove(t1.rt, abs(*(a[x].end() - 1) - *(a[x + 1].begin()) ));
            // cout << '\t' << abs(*(a[x].end() - 1) - *(a[x + 1].begin())) << ' ' << abs(*(a[x].end() - 1) - val) << ' ' << abs(*(a[x + 1].begin()) - val) << endl;
            t1.insert(t1.rt, abs(*(a[x].end() - 1) - val));
            t1.insert(t1.rt, abs(*(a[x + 1].begin()) - val));

            a[x].push_back(val);

            ans = min(ans, val - t2.pre(t2.rt, val));
            ans = min(ans, t2.nxt(t2.rt, val) - val);
            t2.insert(t2.rt, val);

            // for (int i = 1; i <= n; i++, cout << "     ")
            //     for (int j : a[i]) cout << j << ' '; cout << endl;
        } else if (opt == "MIN_GAP") {
            printf("%d\n", t1.get_Min());
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}