#include <bits/stdc++.h>
using namespace std;
long long poww(long long a, long long b, long long md) {
  return (!b ? 1
             : (b & 1 ? a * poww(a * a % md, b / 2, md) % md
                      : poww(a * a % md, b / 2, md) % md));
}
const long long MAXN = 1e6 + 10;
const long long INF = 8e18;
const long long MOD = 1e9 + 7;
set<long long> st;
multiset<long long> LR;
void print_ans() {
  if (st.size() < 3) {
    cout << 0 << '\n';
    return;
  }
  long long mx = *st.rbegin(), mn = *st.begin();
  long long ans = mx - mn - (*LR.rbegin());
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n, q;
  cin >> n >> q;
  while (n--) {
    long long x;
    cin >> x;
    st.insert(x);
  }
  for (auto it = st.begin(); it != st.end(); it++) {
    auto it2 = it;
    it2++;
    if (it2 == st.end()) break;
    LR.insert(*it2 - *it);
  }
  print_ans();
  while (q--) {
    long long tp, x;
    cin >> tp >> x;
    if (tp == 0) {
      auto it = st.find(x);
      auto it2 = it;
      it2++;
      if (it2 != st.end()) LR.erase(LR.find((*it2) - (*it)));
      auto it3 = it;
      if (it != st.begin()) {
        it3--;
        LR.erase(LR.find((*it) - (*it3)));
        if (it2 != st.end()) LR.insert((*it2) - (*it3));
      }
      st.erase(x);
    } else {
      auto it = st.lower_bound(x);
      if (it != st.begin()) {
        auto it2 = it;
        it2--;
        if (it != st.end()) LR.erase(LR.find(*it - *it2));
        LR.insert(x - *it2);
      }
      if (it != st.end()) LR.insert(*it - x);
      st.insert(x);
    }
    print_ans();
  }
  return 0;
}
