#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 200001;
struct E {
  int t, x, _x, a;
} e[kMaxN * 2];
struct V {
  int mn, mx, v;
} v[kMaxN * 4];
int l[kMaxN], p[kMaxN];
int n, q;
void D() {
  for (int i = 1; i <= n + q; i++) {
    l[i] = i;
  }
  sort(l + 1, l + 1 + n + q, [](int i, int j) { return e[i].x < e[j].x; });
  for (int i = 1; i <= n + q; i++) {
    e[l[i]]._x = e[l[i - 1]]._x + (e[l[i]].x != e[l[i - 1]].x);
    p[e[l[i]]._x] = e[l[i]].x;
  }
}
void U(int i, int l, int r, int x, int t) {
  if (l == r) {
    if (t) {
      v[i].mn = v[i].mx = l;
    } else {
      v[i].mn = v[i].mx = 0;
    }
    return;
  }
  int m = (l + r) >> 1;
  if (x <= m) {
    U(i * 2, l, m, x, t);
  } else {
    U(i * 2 + 1, m + 1, r, x, t);
  }
  v[i].mn = v[i * 2].mn ? v[i * 2].mn : v[i * 2 + 1].mn;
  v[i].mx = v[i * 2 + 1].mx ? v[i * 2 + 1].mx : v[i * 2].mx;
  v[i].v = max(v[i * 2].v, v[i * 2 + 1].v);
  if (v[i * 2].mx && v[i * 2 + 1].mn) {
    v[i].v = max(v[i].v, p[v[i * 2 + 1].mn] - p[v[i * 2].mx]);
  }
}
int main() {
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    e[i].t = 1;
    cin >> e[i].x;
  }
  for (int i = n + 1; i <= n + q; i++) {
    cin >> e[i].t >> e[i].x;
  }
  D();
  for (int i = 1; i <= n + q; i++) {
    U(1, 1, n + q, e[i]._x, e[i].t);
    if (i >= n) {
      cout << p[v[1].mx] - p[v[1].mn] - v[1].v << endl;
    }
  }
  return 0;
}
