#include <bits/stdc++.h>
using namespace std;
void solve() {
  int n, qq;
  set<int> p;
  multiset<int> d;
  auto Add = [&](int x) {
    auto ret = p.insert(x);
    assert(ret.second);
    auto it = ret.first;
    if (next(it) != p.end() && it != p.begin()) {
      d.erase(d.find(*next(it) - *prev(it)));
    }
    if (it != p.begin()) {
      d.insert(*it - *prev(it));
    }
    if (next(it) != p.end()) {
      d.insert(*next(it) - *it);
    }
  };
  auto Remove = [&](int x) {
    auto it = p.find(x);
    assert(it != p.end());
    if (next(it) != p.end()) {
      d.erase(d.find(*next(it) - *it));
    }
    if (it != p.begin()) {
      d.erase(d.find(*it - *prev(it)));
    }
    if (next(it) != p.end() && it != p.begin()) {
      d.insert(*next(it) - *prev(it));
    }
    p.erase(it);
  };
  cin >> n >> qq;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    Add(x);
  }
  for (int i = 0; i < qq; i++) {
    if (d.empty())
      cout << 0 << "\n";
    else
      cout << *prev(p.end()) - *p.begin() - *prev(d.end()) << "\n";
    int q, v;
    cin >> q >> v;
    if (q)
      Add(v);
    else
      Remove(v);
  }
  if (d.empty())
    cout << 0 << "\n";
  else
    cout << *prev(p.end()) - *p.begin() - *prev(d.end()) << "\n";
}
int main() {
  int t;
  solve();
  return 0;
}
