#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && (c != '-'))
    ;
  if (c == '-') {
    nega = 1;
    c = getchar();
  }
  x = c - 48;
  while (isdigit(c = getchar())) x = x * 10 + c - 48;
  if (nega) x = -x;
}
template <typename T>
inline void writep(T x) {
  if (x > 9) writep(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  writep(x);
}
template <typename T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
int n, q;
set<int> ps;
multiset<int> gay;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int i, j, t, x, x1, x2;
  cin >> n >> q;
  for (i = 0; i < n; i++) {
    cin >> x;
    ps.insert(x);
  }
  set<int>::iterator it, it1;
  multiset<int>::iterator it3;
  it = ps.begin();
  x1 = *it;
  it++;
  for (; it != ps.end(); it++) {
    x2 = *it;
    gay.insert(x2 - x1);
    x1 = x2;
  }
  if (ps.size() <= 2) {
    cout << 0 << endl;
  } else {
    it = ps.end();
    it--;
    it3 = gay.end();
    it3--;
    cout << *it - *ps.begin() - *it3 << endl;
  }
  while (q--) {
    cin >> t >> x;
    if (t == 1) {
      it = ps.lower_bound(x);
      if (ps.size() > 0) {
        if (it == ps.end()) {
          it--;
          gay.insert(x - *it);
        } else if (it == ps.begin()) {
          gay.insert(*it - x);
        } else {
          x2 = *it;
          it--;
          x1 = *it;
          gay.erase(gay.find(x2 - x1));
          gay.insert(x2 - x);
          gay.insert(x - x1);
        }
      }
      ps.insert(x);
    } else {
      it = ps.lower_bound(x);
      if (ps.size() == 2) {
        gay.clear();
      } else if (ps.size() > 2) {
        it1 = it;
        it1++;
        if (it1 == ps.end()) {
          it--;
          gay.erase(gay.find(x - *it));
        } else if (it == ps.begin()) {
          it++;
          gay.erase(gay.find(*it - x));
        } else {
          it--;
          x1 = *it;
          it++, it++;
          x2 = *it;
          gay.erase(gay.find(x - x1));
          gay.erase(gay.find(x2 - x));
          gay.insert(x2 - x1);
        }
      }
      ps.erase(x);
    }
    if (ps.size() <= 2) {
      cout << 0 << endl;
    } else {
      it = ps.end();
      it--;
      it3 = gay.end();
      it3--;
      cout << *it - *ps.begin() - *it3 << endl;
    }
  }
  return 0;
}
