#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const long long int MOD1 = 1e9 + 7;
const long long int MAX5 = 1e5;
const long long int MAX6 = 1e6;
const long long int MAX7 = 1e7;
const long long int MAX8 = 1e8;
const long long int MAX9 = 1e9;
const long long int MAX10 = 1e10;
const long long int MAXX = 1e18;
long long int pow(long long int x, long long int y) {
  long long int res = 1;
  while (y > 0) {
    res = res * x;
    x = x * x;
    y >>= 1;
  }
  return res;
}
long long int gcd(int a, int b) {
  if (a < b) swap(a, b);
  if (b == 0) return a;
  return gcd(a % b, b);
}
void solve() {
  int n, q;
  cin >> n >> q;
  set<int> p;
  for (int ii = 0; ii < n; ii++) {
    int aa;
    cin >> aa;
    p.insert(aa);
  }
  auto it = p.begin();
  multiset<int> m;
  m.insert(0);
  for (int ii = 0; ii < p.size() - 1; ii++) {
    int x = *it;
    it++;
    m.insert(x - *it);
  }
  cout << *p.rbegin() - *p.begin() + *m.begin();
  cout << "\n";
  ;
  for (int ii = 0; ii < q; ii++) {
    int t, x;
    cin >> t >> x;
    int y, z;
    bool Y = false, Z = false;
    if (t == 0) {
      it = p.find(x);
      if (it != p.begin()) {
        it--;
        y = *it;
        Y = true;
        m.erase(m.find(y - x));
      }
      it = p.find(x);
      if (it != (--p.end())) {
        it++;
        z = *it;
        Z = true;
        m.erase(m.find(x - z));
      }
      if (Y && Z) m.insert(y - z);
      p.erase(x);
    }
    if (t == 1) {
      p.insert(x);
      it = p.find(x);
      if (it != p.begin()) {
        it--;
        y = *it;
        Y = true;
        m.insert(y - x);
      }
      it = p.find(x);
      if (it != (--p.end())) {
        it++;
        z = *it;
        Z = true;
        m.insert(x - z);
      }
      if (Y && Z) m.erase(m.find(y - z));
    }
    if (!p.empty())
      cout << *p.rbegin() - *p.begin() + *m.begin();
    else
      cout << 0;
    cout << "\n";
    ;
  }
}
int main() {
  { solve(); }
}
