#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pi = pair<int, int>;
const int MX = 200005;
const int MOD = (int)(1e9 + 7);
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(ll x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { cout << "]" << endl; }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace output
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vi a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  sort(begin(a), end(a));
  multiset<int> diffs;
  set<int> coords;
  for (int i = 1; i < n; i++) diffs.insert(a[i] - a[i - 1]);
  for (int i = 0; i < n; i++) coords.insert(a[i]);
  auto get = [&]() {
    if (coords.empty()) {
      return 0;
    }
    int fs = *(--coords.end());
    int ss = *(coords.begin());
    int ans = fs - ss;
    if ((int)(diffs).size()) {
      int bdiff = *(--diffs.end());
      ans -= bdiff;
    }
    return ans;
  };
  cout << get() << '\n';
  for (int i = 0; i < q; i++) {
    int t, x;
    cin >> t >> x;
    if (t) {
      auto prev = coords.upper_bound(x);
      auto nxt = coords.upper_bound(x);
      if (prev != coords.begin()) {
        --prev;
        diffs.insert(x - (*prev));
        if (nxt != coords.end()) {
          diffs.erase(diffs.find((*nxt) - (*prev)));
        }
      }
      if (nxt != coords.end()) {
        diffs.insert((*nxt) - x);
      }
      coords.insert(x);
    } else {
      coords.erase(x);
      auto prev = coords.upper_bound(x);
      auto nxt = coords.upper_bound(x);
      if (prev != coords.begin()) {
        --prev;
        diffs.erase(diffs.find(x - (*prev)));
        if (nxt != coords.end()) {
          diffs.insert((*nxt) - (*prev));
        }
      }
      if (nxt != coords.end()) {
        diffs.erase(diffs.find((*nxt) - x));
      }
    }
    cout << get() << '\n';
  }
}
