#include <bits/stdc++.h>
using namespace std;
set<int> v;
multiset<int> diff;
void clean() {
  if (v.size() < 2) {
    cout << 0 << endl;
    return;
  }
  cout << *v.rbegin() - *v.begin() - *diff.rbegin() << endl;
}
int main() {
  v.clear();
  diff.clear();
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    v.insert(x);
  }
  for (auto it = v.begin(); next(it) != v.end(); it++)
    diff.insert(*next(it) - *it);
  clean();
  while (q--) {
    int t, x;
    cin >> t >> x;
    if (t == 1) {
      v.insert(x);
      set<int>::iterator it = v.find(x);
      if (it == v.begin())
        diff.insert(*next(it) - *it);
      else if (next(it) == v.end())
        diff.insert(*it - *prev(it));
      else {
        diff.erase(diff.find(*next(it) - *prev(it)));
        diff.insert(*next(it) - *it);
        diff.insert(*it - *prev(it));
      }
    } else {
      set<int>::iterator it = v.find(x);
      if (v.size() >= 2) {
        if (it == v.begin())
          diff.erase(diff.find(*next(it) - *it));
        else if (next(it) == v.end())
          diff.erase(diff.find(*it - *prev(it)));
        else {
          diff.erase(diff.find(*it - *prev(it)));
          diff.erase(diff.find(*next(it) - *it));
          diff.insert(*next(it) - *prev(it));
        }
      }
      v.erase(it);
    }
    clean();
  }
  return 0;
}
