#include <bits/stdc++.h>
using namespace std;
int32_t main() {
  long long t = 1;
  while (t--) {
    long long n, q;
    cin >> n >> q;
    multiset<long long> wc, r;
    auto get = [&]() -> long long {
      if (wc.size() < 2) return 0;
      return -*r.rbegin() + *wc.rbegin() - *wc.begin();
    };
    vector<long long> a(n);
    for (auto &e : a) cin >> e;
    sort(a.begin(), a.end());
    for (long long i = 0; i < n; i++) {
      if (i) r.insert(a[i] - a[i - 1]);
      wc.insert(a[i]);
    }
    cout << get() << "\n";
    while (q--) {
      long long t, x;
      cin >> t >> x;
      if (t == 1) {
        wc.insert(x);
        auto it = wc.find(x);
        if (next(it) != wc.end() && it != wc.begin())
          r.erase(r.find(*next(it) - *prev(it)));
        if (it != wc.begin()) r.insert(*it - *prev(it));
        if (next(it) != wc.end()) r.insert(*next(it) - *it);
      } else {
        auto it = wc.find(x);
        if (next(it) != wc.end()) r.erase(r.find(*next(it) - *it));
        if (it != wc.begin()) r.erase(r.find(*it - *prev(it)));
        if (next(it) != wc.end() && it != wc.begin())
          r.insert(*next(it) - *prev(it));
        wc.erase(it);
      }
      cout << get() << "\n";
    }
  }
  return 0;
}
