#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double pi = acos(-1.0);
const double G = 6.67430e-11;
int n, q;
set<int> p;
multiset<int> d;
void in(int x) {
  p.insert(x);
  if (p.size() == 1) return;
  auto pos = p.find(x);
  if (pos == --p.end()) {
    d.insert(x - *--pos);
  } else if (pos == p.begin()) {
    int y = *++pos;
    d.insert(y - x);
  } else {
    auto r = ++pos;
    pos--;
    auto l = --pos;
    pos++;
    d.insert(x - *l);
    d.insert(*r - x);
    d.erase(d.find(*r - *l));
  }
}
void er(int x) {
  set<int>::iterator pos;
  pos = p.find(x);
  if (p.size() < 2) {
    p.erase(x);
    return;
  }
  if (pos == --p.end())
    d.erase(d.find(x - *--pos));
  else if (pos == p.begin())
    d.erase(d.find(*++pos - x));
  else {
    set<int>::iterator l;
    set<int>::iterator r;
    l = --pos;
    ++pos;
    r = ++pos;
    --pos;
    d.erase(d.find(x - *l));
    d.erase(d.find(*r - x));
    d.insert(*r - *l);
  }
  p.erase(x);
}
int kk() {
  if (p.size() <= 2) return 0;
  auto l = p.begin();
  auto r = --p.end();
  return (*r - *l - *--d.end());
}
int main() {
  cin >> n >> q;
  int x;
  for (int i = 1; i <= n; ++i) {
    cin >> x;
    in(x);
  }
  cout << kk() << "\n";
  int op;
  while (q--) {
    cin >> op >> x;
    if (op == 1)
      in(x);
    else
      er(x);
    cout << kk() << "\n";
  }
}
