#include <bits/stdc++.h>
using namespace std;
void TestCase() {
  int n, q;
  cin >> n >> q;
  set<int> st;
  vector<int> v(n);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    v[i] = x;
    st.insert(x);
  }
  multiset<int> mst;
  sort(v.begin(), v.end());
  for (int i = 1; i < n; i++) {
    mst.insert(v[i] - v[i - 1]);
  }
  if (st.size() > 2)
    cout << *(prev(st.end())) - *st.begin() - *(prev(mst.end())) << "\n";
  else
    cout << 0 << "\n";
  while (q--) {
    int query;
    cin >> query;
    if (query == 1) {
      int x;
      cin >> x;
      st.insert(x);
      auto it = st.lower_bound(x);
      int res = 0;
      if (it != st.begin()) {
        res++;
      }
      if (it != prev(st.end())) {
        res++;
      }
      if (res == 2) {
        auto a = prev(it);
        auto b = next(it);
        auto i = mst.lower_bound(*b - *a);
        mst.erase(i);
      }
      if (it != st.begin()) {
        auto a = prev(it);
        mst.insert(x - *a);
      }
      if (it != prev(st.end())) {
        auto b = next(it);
        mst.insert(*b - x);
      }
      if (st.size() > 2)
        cout << *(prev(st.end())) - *st.begin() - *(prev(mst.end())) << "\n";
      else
        cout << 0 << "\n";
    } else if (query == 0) {
      int x;
      cin >> x;
      auto it = st.lower_bound(x);
      int res = 0;
      if (it != st.begin()) {
        res++;
        auto a = prev(it);
        auto l = mst.lower_bound(x - *a);
        mst.erase(l);
      }
      if (it != prev(st.end())) {
        res++;
        auto b = next(it);
        auto r = mst.lower_bound(*b - x);
        mst.erase(r);
      }
      if (res == 2) {
        auto a = prev(it);
        auto b = next(it);
        mst.insert(*b - *a);
      }
      st.erase(x);
      if (st.size() > 2)
        cout << *(prev(st.end())) - *st.begin() - *(prev(mst.end())) << "\n";
      else
        cout << 0 << "\n";
    }
  }
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  TestCase();
}
