#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  set<int> v;
  map<int, int> gaps;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    v.insert(x);
  }
  for (auto i = v.begin(); i != v.end();) {
    auto j = i;
    if (++i == v.end()) break;
    ++gaps[*i - *j];
  }
  if (n > 2)
    cout << *v.rbegin() - *v.begin() - gaps.rbegin()->first << '\n';
  else
    cout << 0 << '\n';
  for (int qq = 0; qq < q; ++qq) {
    int c, x;
    cin >> c >> x;
    if (c) {
      auto f = v.upper_bound(x);
      if (v.size() >= 1) {
        if (f == v.end()) {
          ++gaps[x - *v.rbegin()];
        } else {
          ++gaps[*f - x];
          if (f != v.begin() && v.size() >= 2) {
            auto g = f;
            f--;
            ++gaps[x - *f];
            --gaps[*g - *f];
            if (gaps[*g - *f] <= 0) gaps.erase(*g - *f);
          }
        }
      }
      v.insert(x);
    } else {
      auto f = v.find(x);
      auto z = v.end();
      z--;
      if (v.size() > 1) {
        if (x == *v.begin()) {
          f++;
          --gaps[*f - x];
          if (gaps[*f - x] <= 0) gaps.erase(*f - x);
        } else if (x == *v.rbegin()) {
          f--;
          --gaps[x - *f];
          if (gaps[x - *f] <= 0) gaps.erase(x - *f);
        } else if (v.size() > 2) {
          auto g = f;
          f--;
          g++;
          --gaps[x - *f];
          if (gaps[x - *f] <= 0) gaps.erase(x - *f);
          --gaps[*g - x];
          if (gaps[*g - x] <= 0) gaps.erase(*g - x);
          ++gaps[*g - *f];
        }
      }
      v.erase(x);
    }
    if (v.size() > 2)
      cout << *v.rbegin() - *v.begin() - gaps.rbegin()->first << endl;
    else
      cout << 0 << endl;
  }
  return 0;
}
