#include <bits/stdc++.h>
using namespace std;
int n, q;
set<int> a;
multiset<int> d;
void add(int x) {
  set<int>::iterator it = a.lower_bound(x);
  if (it != a.begin() && it != a.end())
    d.erase(d.lower_bound((*it) - (*prev(it))));
  if (it != a.begin()) d.insert(x - (*prev(it)));
  if (it != a.end()) d.insert((*it) - x);
  a.insert(it, x);
}
void del(int x) {
  set<int>::iterator it = a.lower_bound(x);
  it = a.erase(it);
  if (it != a.begin()) d.erase(d.lower_bound(x - (*prev(it))));
  if (it != a.end()) d.erase(d.lower_bound((*it - x)));
  if (it != a.begin() && it != a.end()) d.insert((*it) - (*prev(it)));
}
int calc() {
  if (a.size() <= 2) return 0;
  return *a.rbegin() - *a.begin() - *d.rbegin();
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 0, x; i < n; i++) {
    scanf("%d", &x);
    add(x);
  }
  printf("%d\n", calc());
  while (q--) {
    int op, x;
    scanf("%d%d", &op, &x);
    if (op == 0)
      del(x);
    else if (op == 1)
      add(x);
    printf("%d\n", calc());
  }
  return 0;
}
