#include <bits/stdc++.h>
using namespace std;
set<long long int> elmt;
multiset<long long int, greater<long long int>> diff;
int main() {
  set<long long int>::iterator it, nextit, previt;
  multiset<long long int, greater<long long int>>::iterator ter;
  long long int n, q, i, x, prev = -1, f, l, mval, a;
  cin >> n >> q;
  for (i = 0; i < n; i++) {
    cin >> x;
    elmt.insert(x);
  }
  for (auto itr = elmt.begin(); itr != elmt.end(); itr++) {
    if (prev == -1)
      f = *itr;
    else
      diff.insert(*itr - prev);
    prev = *itr;
  }
  l = prev;
  mval = *(diff.begin());
  cout << l - f - mval << endl;
  for (i = 0; i < q; i++) {
    cin >> a >> x;
    if (a == 0) {
      it = elmt.find(x);
      previt = elmt.find(x);
      previt--;
      nextit = elmt.find(x);
      nextit++;
      if (it != elmt.begin()) {
        ter = diff.find(*it - *previt);
        diff.erase(ter);
      } else {
        if (nextit != elmt.end())
          f = *nextit;
        else
          f = 0;
      }
      if (nextit != elmt.end()) {
        ter = diff.find(*nextit - *it);
        diff.erase(ter);
      } else {
        if (it != elmt.begin())
          l = *previt;
        else
          l = 0;
      }
      if (it != elmt.begin() && nextit != elmt.end())
        diff.insert(*nextit - *previt);
      elmt.erase(x);
    } else {
      elmt.insert(x);
      it = elmt.find(x);
      previt = elmt.find(x);
      previt--;
      nextit = elmt.find(x);
      nextit++;
      if (nextit != elmt.end() && it != elmt.begin()) {
        ter = diff.find(*nextit - *previt);
        diff.erase(ter);
      }
      if (it != elmt.begin())
        diff.insert(*it - *previt);
      else
        f = *it;
      if (nextit != elmt.end())
        diff.insert(*nextit - *it);
      else
        l = *it;
    }
    mval = *(diff.begin());
    cout << l - f - mval << endl;
  }
  return 0;
}
