#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  set<int> s;
  multiset<int> d;
  auto Add = [&](int x) {
    auto ret = s.insert(x);
    auto it = ret.first;
    if (next(it) != s.end() && it != s.begin()) {
      d.erase(d.find(*next(it) - *prev(it)));
    }
    if (it != s.begin()) {
      d.insert(*it - *prev(it));
    }
    if (next(it) != s.end()) {
      d.insert(*next(it) - *it);
    }
  };
  auto Remove = [&](int x) {
    auto it = s.find(x);
    if (it != s.begin()) {
      d.erase(d.find(*it - *prev(it)));
    }
    if (next(it) != s.end()) {
      d.erase(d.find(*next(it) - *it));
    }
    if (next(it) != s.end() && it != s.begin()) {
      d.insert(*next(it) - *prev(it));
    }
    s.erase(it);
  };
  for (int i = 0; i < n; i++) {
    int foo;
    cin >> foo;
    Add(foo);
  }
  for (int i = 0; i <= q; i++) {
    if (d.empty()) {
      cout << 0 << '\n';
    } else {
      cout << *prev(s.end()) - *s.begin() - *prev(d.end()) << '\n';
    }
    if (i == q) {
      break;
    }
    int c, x;
    cin >> c >> x;
    if (c) {
      Add(x);
    } else {
      Remove(x);
    }
  }
  return 0;
}
