#include <bits/stdc++.h>
int main() {
  int n, q;
  scanf("%d", &n);
  scanf("%d", &q);
  int i;
  long ans[q + 1];
  long val;
  std::set<long> valores;
  for (i = 0; i < n; i++) {
    scanf("%ld", &val);
    valores.insert(val);
  }
  std::set<long>::iterator ite;
  std::multiset<long> dife;
  for (ite = valores.begin(); ite != --valores.end(); ite++) {
    dife.insert(*valores.upper_bound(*ite) - *ite);
  }
  int acc;
  std::set<long>::iterator low, up;
  for (i = 0; i < q; i++) {
    if (valores.size() > 1)
      ans[i] = *valores.rbegin() - *valores.begin() - *dife.rbegin();
    else
      ans[i] = 0;
    scanf("%d", &acc);
    scanf("%ld", &val);
    if (acc == 0) {
      up = valores.upper_bound(val);
      low = valores.lower_bound(val);
      if (up != valores.end()) {
        dife.erase(dife.lower_bound(*up - val));
      }
      if (low != valores.begin()) {
        low--;
        dife.erase(dife.lower_bound(val - *low));
        low++;
      }
      if ((up != valores.end()) && (low != valores.begin())) {
        low--;
        dife.insert(*up - *low);
      }
      valores.erase(val);
    } else {
      up = valores.upper_bound(val);
      low = valores.lower_bound(val);
      if (up != valores.end()) {
        dife.insert(*up - val);
      }
      if (low != valores.begin()) {
        low--;
        dife.insert(val - *low);
        low++;
      }
      if ((up != valores.end()) && (low != valores.begin())) {
        low--;
        dife.erase(dife.lower_bound(*up - *low));
      }
      valores.insert(val);
    }
  }
  if (valores.size() > 1)
    ans[q] = *valores.rbegin() - *valores.begin() - *dife.rbegin();
  else
    ans[q] = 0;
  for (i = 0; i < q + 1; i++) {
    printf("%d \n", ans[i]);
  }
  return 0;
}
