rt，就看了这一题，用权值线段树做的

#include <iostream>
#include <cmath>

using namespace std;

const int N = 1000010;
const int INF = -1145141;

struct SegmentTree {
    int l, r;
    int dat, ldat, rdat;
    int sum;
} t[N << 2];

int n, q;
int a[N], b[N], c[N * 2];

void pushup(SegmentTree &fa, SegmentTree ls, SegmentTree rs) {
    if (ls.ldat != 0 && rs.ldat != 0) {
        fa.dat = ls.dat + rs.dat + rs.ldat - ls.rdat;
        fa.ldat = ls.ldat, fa.rdat = rs.rdat;
    }
    else if (ls.ldat != 0) fa.dat = ls.dat, fa.ldat = ls.ldat, fa.rdat = ls.rdat;
    else if (rs.ldat != 0) fa.dat = rs.dat, fa.ldat = rs.ldat, fa.rdat = rs.rdat;
    else fa.dat = fa.ldat = fa.rdat = 0;
    fa.sum = ls.sum + rs.sum;
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) { t[p].dat = t[p].ldat = t[p].rdat = t[p].sum = 0; return; }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build((p << 1) | 1, mid + 1, r);
    pushup(t[p], t[p << 1], t[(p << 1) | 1]);
}

int ask(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) return t[p].sum;
    int mid = (t[p].l + t[p].r) >> 1, val = 0;
    if (l <= mid) val += ask(p << 1, l, r);
    if (r > mid) val += ask((p << 1) | 1, l, r);
    return val;
}

int ask_left(int p, int l, int r) {
    if (t[p].l == t[p].r) return t[p].l;
    int mid = (l + r) >> 1;
    if (l <= mid && ask(1, l, mid)) return ask_left(p << l, l, r);
    else if (r > mid && ask(1, mid + 1, r)) return ask_left((p << 1) | 1, l, r);
    return 0;
}

int ask_right(int p, int l, int r) {
    if (t[p].l == t[p].r) return t[p].l;
    int mid = (l + r) >> 1;
    if (r > mid && ask(1, mid + 1, r)) return ask_right((p << 1) | 1, l, r);
    else if (l <= mid && ask(1, l, mid)) return ask_right(p << l, l, r);
    return 0;
}

void change(int p, int x, int v) {
    if (t[p].l == t[p].r) {
        t[p].sum += v;
        if (t[p].sum) t[p].ldat = t[p].rdat = t[p].l;
        else t[p].ldat = t[p].rdat = 0;
        return;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if (x <= mid) change(p << 1, x, v);
    if (x > mid) change((p << 1) | 1, x, v);
    pushup(t[p], t[p << 1], t[(p << 1) | 1]);
}

int main() {
    scanf("%d%d", &n, &q);
    build(1, 1, 1000001);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        change(1, x + 1, 1);
    }
    while (q--) {
        int opt, x; scanf("%d%d", &opt, &x);
        x++;
        if (opt == 2) change(1, x, 1);
        else {
            if (!ask(1, x, x)) {
                puts("-1");
                continue;
            }
            change(1, x, -1);
        }
        // cout << t[1].dat << "\n";
        printf("%d\n", t[1].dat + abs(ask_left(1, 1, 1000001) - ask_right(1, 1, 1000001)));
    }
    return 0;
}