#include <bits/stdc++.h>
using namespace std;
long long int mod1 = 998244353, mod2 = (long long int)1e9 + 7;
long long int power(long long int n, long long int k, long long int mod) {
  long long int ans = 1;
  n = n % mod;
  while (k > 0) {
    if (k & 1) ans = (ans * n) % mod;
    n = (n * n) % mod;
    k >>= 1;
  }
  return (ans + mod) % mod;
}
struct triplet {
  long long int a, b, c;
};
bool operator<(const triplet &t1, const triplet &t2) {
  if (t1.a < t2.a) return true;
  if (t1.a == t2.a && t1.b < t2.b) return true;
  if (t1.a == t2.a && t1.b == t2.b && t1.c < t2.c) return true;
  return false;
}
int32_t main() {
  long long int testcases = 1;
  while (testcases--) {
    long long int n, q;
    cin >> n >> q;
    set<long long int> p;
    for (long long int i = 0; i < n; i++) {
      long long int x;
      cin >> x;
      p.insert(x);
    }
    multiset<long long int> ms;
    auto it1 = p.begin(), it2 = it1;
    ++it2;
    for (long long int i = 1; i < n; i++) {
      ms.insert(*it2 - *it1);
      it1++, ++it2;
    }
    if (p.size() <= 1)
      cout << 0 << "\n";
    else
      cout << (*p.rbegin() - *p.begin()) - *ms.rbegin() << "\n";
    for (long long int i = 0; i < q; i++) {
      long long int opn, x;
      cin >> opn >> x;
      if (opn == 1) {
        if (p.size() == 0) {
        } else if (x < *p.begin())
          ms.insert(*p.begin() - x);
        else if (x > *p.rbegin())
          ms.insert(x - *p.rbegin());
        else {
          auto it = p.upper_bound(x);
          auto it1 = prev(it);
          ms.erase(ms.find(*it - *it1));
          ms.insert(*it - x), ms.insert(x - *it1);
        }
        p.insert(x);
      } else if (opn == 0) {
        auto it = p.find(x);
        if (p.size() == 1) {
        } else if (it == p.begin()) {
          auto nx = next(it);
          ms.erase(ms.find(*nx - *it));
        } else if (x == *p.rbegin()) {
          auto pv = prev(it);
          ms.erase(ms.find(*it - *pv));
        } else {
          auto nx = next(it);
          ms.erase(ms.find(*nx - *it));
          auto pv = prev(it);
          ms.erase(ms.find(*it - *pv));
          ms.insert(*nx - *pv);
        }
        p.erase(it);
      }
      if (p.size() <= 1)
        cout << 0 << "\n";
      else
        cout << (*p.rbegin() - *p.begin()) - *ms.rbegin() << "\n";
    }
  }
}
