#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, nq;
  cin >> n >> nq;
  set<int> p;
  multiset<int> d;
  auto add = [&](int x) {
    auto it = p.insert(x).first;
    auto nt = next(it);
    if (it == p.begin()) {
      if (nt != p.end()) d.insert(*nt - x);
    } else if (nt == p.end()) {
      d.insert(x - *prev(it));
    } else {
      auto lt = prev(it);
      d.erase(d.find(*nt - *lt));
      d.insert(x - *lt);
      d.insert(*nt - x);
    }
  };
  auto del = [&](int x) {
    auto it = p.erase(p.find(x));
    if (it == p.end()) {
      if (p.rbegin() != p.rend()) d.erase(d.find(x - *p.rbegin()));
    } else if (it == p.begin()) {
      d.erase(d.find(*it - x));
    } else {
      int l = *prev(it), r = *it;
      d.erase(d.find(r - x));
      d.erase(d.find(x - l));
      d.insert(r - l);
    }
  };
  for (int i = 0, x; i < n; i++) {
    cin >> x;
    add(x);
  }
  auto solve = [&]() {
    if (p.size() <= 2) return 0;
    return *p.rbegin() - *p.begin() - *d.rbegin();
  };
  cout << solve() << '\n';
  for (int t, x, dx; nq--;) {
    cin >> t >> x;
    if (t)
      add(x);
    else
      del(x);
    cout << solve() << '\n';
  }
  return 0;
}
