#include <bits/stdc++.h>
using namespace std;
void ad(int a, set<int> &x, multiset<int> &d) {
  x.insert(a);
  set<int>::iterator it = x.find(a);
  int pit = -1, nit = -1;
  if (it != x.begin()) {
    --it;
    d.insert(a - *it);
    pit = *it;
    ++it;
  }
  ++it;
  if (it != x.end()) {
    d.insert(*it - a);
    nit = *it;
  }
  if (nit != -1 && pit != -1) {
    d.erase(d.find(nit - pit));
  }
}
void rem(int a, set<int> &x, multiset<int> &d) {
  set<int>::iterator it = x.find(a);
  int pit = -1, nit = -1;
  if (it != x.begin()) {
    --it;
    d.erase(d.find(a - *it));
    pit = *it;
    ++it;
  }
  ++it;
  if (it != x.end()) {
    d.erase(d.find(*it - a));
    nit = *it;
  }
  x.erase(a);
  if (nit != -1 && pit != -1) {
    d.insert(nit - pit);
  }
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  int n, q;
  cin >> n >> q;
  set<int> x;
  multiset<int> d;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    ad(a, x, d);
  }
  if (d.empty())
    cout << 0 << '\n';
  else
    cout << *(--x.end()) - *x.begin() - *(--d.end()) << '\n';
  while (q--) {
    int t, a;
    cin >> t >> a;
    if (t == 0) {
      rem(a, x, d);
    } else {
      ad(a, x, d);
    }
    if (d.empty())
      cout << 0 << '\n';
    else
      cout << *(--x.end()) - *x.begin() - *(--d.end()) << '\n';
  }
}
