#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, q, p, t, x;
  cin >> n >> q;
  set<int> st;
  set<pair<int, int>> sp;
  for (int i = 0; i < n; i++) {
    cin >> p;
    st.insert(p);
  }
  auto s = st.begin(), e = st.end();
  e--;
  for (auto it = s; it != e; it++) {
    auto nxt = it;
    nxt++;
    sp.insert(make_pair(*nxt - *it, *it));
  }
  if (!sp.empty()) {
    cout << *st.rbegin() - *st.begin() - (*sp.rbegin()).first << "\n";
  } else {
    cout << *st.rbegin() - *st.begin() << "\n";
  }
  while (q--) {
    cin >> t >> x;
    if (t == 0) {
      auto it = st.find(x);
      auto prev = it, next = it;
      if (it == st.begin()) {
        next++;
        if (next != st.end()) {
          sp.erase(make_pair(*next - x, x));
        }
      } else {
        prev--, next++;
        if (next == st.end()) {
          sp.erase(make_pair(*it - *prev, *prev));
        } else {
          sp.erase(make_pair(*next - *it, *it));
          sp.erase(make_pair(*it - *prev, *prev));
          sp.insert(make_pair(*next - *prev, *prev));
        }
      }
      st.erase(x);
    } else {
      st.insert(x);
      auto it = st.find(x);
      auto prev = it, next = it;
      if (it == st.begin()) {
        next++;
        if (next != st.end()) {
          sp.insert(make_pair(*next - *it, *it));
        }
      } else {
        prev--, next++;
        if (next == st.end()) {
          sp.insert(make_pair(*it - *prev, *prev));
        } else {
          sp.erase(make_pair(*next - *prev, *prev));
          sp.insert(make_pair(*it - *prev, *prev));
          sp.insert(make_pair(*next - *it, *it));
        }
      }
    }
    if (!st.empty()) {
      if (!sp.empty()) {
        cout << *st.rbegin() - *st.begin() - (*sp.rbegin()).first << "\n";
      } else {
        cout << *st.rbegin() - *st.begin() << "\n";
      }
    } else {
      cout << "0\n";
    }
  }
  return 0;
}
