#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vll = vector<long long>;
using vpi = vector<pair<int, int>>;
using pii = pair<int, int>;
const char nl = '\n';
string to_string(char c) { return string(1, c); }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < ((int)v.size()); ++i) res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t SZ>
string to_string(bitset<SZ> b) {
  string res = "";
  for (int i = 0; i < (SZ); ++i) res += char('0' + b[i]);
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p);
template <class T>
string to_string(T& v) {
  bool fst = 1;
  string res = "{";
  for (const auto& x : v) {
    if (!fst) res += ", ";
    fst = 0;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, q;
  cin >> n >> q;
  vector<int> vals(n);
  for (int i = 0; i < n; i++) {
    cin >> vals[i];
  }
  sort(vals.begin(), vals.end());
  set<pair<int, int>> diffs;
  set<int> p;
  for (int i = 0; i < n; i++) {
    p.insert(vals[i]);
    if (i < n - 1) {
      diffs.insert({vals[i] - vals[i + 1], vals[i]});
    }
  }
  auto get = [&]() -> int {
    if (p.size() <= 2) {
      return 0;
    }
    int sub = min(diffs.begin()->first, 0);
    return *p.rbegin() - *p.begin() + sub;
  };
  cout << get() << nl;
  while (q--) {
    int t, x;
    cin >> t >> x;
    if (t == 0) {
      auto it = p.find(x);
      int left = -1;
      int right = -1;
      if (it != prev(p.end())) {
        auto nxt = next(it);
        if (nxt != p.end()) {
          right = *nxt;
          diffs.erase({*it - *nxt, *it});
        }
      }
      if (it != p.begin()) {
        auto prv = prev(it);
        left = *prv;
        diffs.erase({*prv - *it, *prv});
      }
      if (left != -1 && right != -1) {
        diffs.insert({left - right, left});
      }
      p.erase(it);
    } else {
      auto it = p.lower_bound(x);
      int left = -1;
      int right = -1;
      if (it != p.end()) {
        right = *it;
        diffs.insert({x - *it, x});
      }
      if (it != p.begin()) {
        auto prv = prev(it);
        left = *prv;
        diffs.insert({*prv - x, *prv});
      }
      if (left != -1 && right != -1) {
        diffs.erase({left - right, left});
      }
      p.insert(x);
    }
    cout << get() << nl;
  }
  return 0;
}
