#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
int n;
int Q;
void init() {
  scanf("%d%d", &n, &Q);
  for (int i = 0; i < n; ++i) scanf("%d", a + i);
}
void sol() {
  multiset<int> st;
  multiset<int> dif;
  for (int i = 0; i < n; ++i) st.insert(a[i]);
  sort(a, a + n);
  for (int i = 1; i < n; ++i) dif.insert(a[i] - a[i - 1]);
  int ans;
  if (st.size() <= 2)
    ans = 0;
  else
    ans = (*(st.rbegin()) - *(st.begin())) - (*(dif.rbegin()));
  printf("%d\n", ans);
  int op, x;
  while (Q--) {
    scanf("%d%d", &op, &x);
    if (op == 0) {
      auto it = st.lower_bound(x);
      auto it1 = it;
      int tmp;
      if (it != st.begin()) {
        it1 = it;
        --it1;
        tmp = *it - *it1;
        auto ti = dif.lower_bound(tmp);
        dif.erase(ti);
      }
      it1 = it;
      ++it1;
      if (it1 != st.end()) {
        tmp = *it1 - *it;
        dif.erase(dif.lower_bound(tmp));
      }
      if (it1 != st.end() && it != st.begin()) {
        auto it2 = it;
        --it2;
        dif.insert(*it1 - *it2);
      }
      st.erase(it);
    } else {
      st.insert(x);
      auto it = st.lower_bound(x);
      auto it1 = it;
      if (it != st.begin()) {
        it1 = it;
        --it1;
        dif.insert(*it - *it1);
      }
      it1 = it;
      ++it1;
      if (it1 != st.end()) {
        dif.insert(*it1 - *it);
      }
      if (it != st.begin() && it1 != st.end()) {
        --it;
        int tmp = *it1 - *it;
        dif.erase(dif.lower_bound(tmp));
      }
    }
    if (st.size() <= 2)
      ans = 0;
    else
      ans = (*(st.rbegin()) - *(st.begin())) - (*(dif.rbegin()));
    printf("%d\n", ans);
  }
}
int main() {
  int T;
  {
    init();
    sol();
  }
  return 0;
}
