#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  multiset<int> ok;
  set<int> s;
  int n, k, i, a, j, l, u, p, ss, b, aa, bb;
  cin >> n >> k;
  for (i = 0; i < n; i++) {
    cin >> a;
    s.insert(a);
  }
  u = *s.begin();
  for (auto g : s) {
    if (g != u) ok.insert(g - u);
    u = g;
  }
  if (s.size() > 2)
    cout << (*s.rbegin() - *s.begin() - *ok.rbegin()) << endl;
  else
    cout << 0 << endl;
  while (k--) {
    cin >> a >> b;
    if (a == 1) {
      s.insert(b);
      auto p = s.find(b);
      if (p == s.begin()) {
        aa = *p;
        bb = aa;
        p++;
        if (p != s.end()) bb = *p;
        if (aa != bb) ok.insert(bb - aa);
      } else if (++p == s.end()) {
        p--;
        aa = *p;
        bb = aa;
        if (p != s.begin()) {
          p--;
          bb = *p;
        }
        if (aa != bb) ok.insert(aa - bb);
      } else {
        --p;
        aa = *(--p);
        ok.insert(b - aa);
        p++;
        p++;
        bb = *(p);
        ok.insert(bb - b);
        ok.erase(ok.find(bb - aa));
      }
    } else {
      auto p = s.find(b);
      if (p == s.begin()) {
        aa = b;
        bb = aa;
        p++;
        if (p != s.end()) bb = *p;
        if (aa != bb) ok.erase(ok.find(bb - aa));
      } else if (++p == s.end()) {
        p--;
        aa = b;
        bb = aa;
        if (p != s.begin()) {
          p--;
          bb = *p;
        }
        if (aa != bb) ok.erase(ok.find(aa - bb));
      } else {
        p--;
        aa = *(--p);
        ok.erase(ok.find(b - aa));
        p++;
        p++;
        bb = *(p);
        ok.erase(ok.find(bb - b));
        ok.insert(bb - aa);
      }
      s.erase(s.find(b));
    }
    if (s.size() > 2)
      cout << (*s.rbegin() - *s.begin() - *ok.rbegin()) << endl;
    else
      cout << 0 << endl;
  }
}
