#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long maxn = 3e5 + 123;
const long long inf = 1e9 + 123;
const long long linf = 1e18 + 123;
const long long mod = 1e9 + 7;
const double eps = 1e-9;
const double pi = acos(-1);
int dx[8] = {0, 1, -1, 0, 1, -1, 1, -1};
int dy[8] = {1, 0, 0, -1, 1, 1, -1, -1};
set<long long> s, s1;
map<long long, long long> m, mm;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    s.insert(x);
  }
  long long last = -1;
  for (auto i : s) {
    if (last == -1) {
      last = i;
      continue;
    }
    s1.insert(i - last);
    m[i - last]++;
    mm[i] = last;
    last = i;
  }
  if (n == 1) {
    cout << "0\n";
  } else {
    cout << (*s.rbegin()) - (*s.begin()) - (*s1.rbegin()) << "\n";
  }
  while (q--) {
    long long t, pos;
    cin >> t >> pos;
    if (s.size() == 0) {
      s.insert(pos);
      cout << "0\n";
      continue;
    }
    if (t == 1 && (*s.begin()) > pos) {
      s1.insert((*s.begin()) - pos);
      m[(*s.begin()) - pos]++;
      mm[(*s.begin())] = pos;
      s.insert(pos);
    } else if (t == 0 && (*s.begin()) == pos) {
      s.erase(pos);
      m[(*s.begin()) - pos]--;
      if (m[(*s.begin()) - pos] == 0) {
        s1.erase((*s.begin() - pos));
      }
      mm[(*s.begin())] = 0;
    } else if (t == 1 && (*s.rbegin()) < pos) {
      s1.insert(pos - (*s.rbegin()));
      m[pos - (*s.rbegin())]++;
      mm[pos] = (*s.rbegin());
      s.insert(pos);
    } else if (t == 0 && (*s.rbegin()) == pos) {
      s.erase(pos);
      mm[pos] = 0;
      m[pos - (*s.rbegin())]--;
      if (m[pos - (*s.rbegin())] == 0) {
        s1.erase(pos - (*s.rbegin()));
      }
    } else {
      long long w = (*s.upper_bound(pos));
      long long w1 = mm[w];
      if (t == 1) {
        m[w - w1]--;
        if (m[w - w1] == 0) {
          s1.erase(w - w1);
        }
        s1.insert(w - pos);
        m[w - pos]++;
        s1.insert(pos - w1);
        m[pos - w1]++;
        mm[w] = pos;
        mm[pos] = w1;
        s.insert(pos);
      } else {
        w1 = mm[pos];
        m[w - pos]--;
        if (m[w - pos] == 0) {
          s1.erase(w - pos);
        }
        m[pos - w1]--;
        if (m[pos - w1] == 0) {
          s1.erase(pos - w1);
        }
        mm[pos] = 0;
        s.erase(pos);
        mm[w] = w1;
        m[w - w1]++;
        s1.insert(w - w1);
      }
    }
    if (s.size() <= 1) {
      cout << "0\n";
      continue;
    }
    cout << (*s.rbegin()) - (*s.begin()) - (*s1.rbegin()) << "\n";
  }
  exit(0);
}
