#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using pdd = pair<double, double>;
using pil = pair<int, ll>;
int n;
set<int> st;
multiset<int> sub;
void go() {
  if (st.size() <= 2) {
    cout << 0 << "\n";
    return;
  }
  int big = *st.rbegin();
  int small = *st.begin();
  int z = *sub.rbegin();
  cout << big - small - z << "\n";
}
void erase(int y) {
  st.erase(y);
  if (st.empty()) {
    sub.clear();
    return;
  }
  int big = *st.rbegin();
  int small = *st.begin();
  if (y > big) {
    sub.erase(sub.find(y - big));
  } else if (y < small) {
    sub.erase(sub.find(small - y));
  } else {
    auto t1 = st.lower_bound(y);
    auto t2 = prev(t1);
    sub.erase(sub.find(y - *t2));
    sub.erase(sub.find(*t1 - y));
    sub.insert(*t1 - *t2);
  }
}
void insert(int y) {
  if (st.empty()) {
    st.insert(y);
    return;
  }
  int big = *st.rbegin();
  int small = *st.begin();
  if (y > big) {
    sub.insert(y - big);
  } else if (y < small) {
    sub.insert(small - y);
  } else {
    auto t1 = st.lower_bound(y);
    auto t2 = prev(t1);
    sub.erase(sub.find(*t1 - *t2));
    sub.insert(y - *t2);
    sub.insert(*t1 - y);
  }
  st.insert(y);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    insert(x);
  }
  go();
  while (q--) {
    ll x, y;
    cin >> x >> y;
    if (x == 0)
      erase(y);
    else
      insert(y);
    go();
  }
}
