#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, q;
  cin >> n >> q;
  multiset<int> p, dif;
  for (int i = 0; i < n; i++) {
    int trash;
    cin >> trash;
    p.insert(trash);
  }
  for (auto i = p.begin(); i != prev(p.end()); ++i) {
    dif.insert(*next(i) - *i);
  }
  int mindif = 0, maxdif = *p.rbegin() - *p.begin();
  if (!dif.empty()) mindif = *dif.rbegin();
  cout << maxdif - mindif << endl;
  while (q--) {
    int t, x;
    cin >> t >> x;
    if (t) p.insert(x);
    auto itr = p.find(x);
    int pl = 0, pr = 0;
    if (itr != p.begin()) {
      pl = *prev(itr);
    }
    if (itr != prev(p.end())) {
      pr = *next(itr);
    }
    if (!t) {
      if (pl) dif.erase(dif.find(x - pl));
      if (pr) dif.erase(dif.find(pr - x));
      p.erase(x);
      if (pr && pl) dif.insert(pr - pl);
    } else {
      if (pl && pr) dif.erase(dif.find(pr - pl));
      if (pr) dif.insert(pr - x);
      if (pl) dif.insert(x - pl);
    }
    if (p.empty()) {
      cout << 0 << endl;
      continue;
    }
    maxdif = *p.rbegin() - *p.begin();
    if (!dif.empty())
      mindif = *dif.rbegin();
    else
      mindif = 0;
    cout << maxdif - mindif << endl;
  }
  return 0;
}
