#include <bits/stdc++.h>
using namespace std;
set<int> s;
multiset<int, greater<int>> ms;
const int N = 100010;
int sz[N], n, q;
int main(void) {
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> sz[i];
    s.insert(sz[i]);
  }
  sort(sz + 1, sz + n + 1);
  ms.insert(0);
  for (int i = 2; i <= n; i++) ms.insert(sz[i] - sz[i - 1]);
  if (s.size() <= 2)
    cout << 0 << endl;
  else {
    set<int>::iterator ed = s.end(), st = s.begin();
    ed--;
    cout << *ed - *st - *ms.begin() << endl;
  }
  for (int i = 1; i <= q; i++) {
    int a, b;
    cin >> a >> b;
    if (a == 1) {
      s.insert(b);
      if (s.size() == 1) {
        cout << 0 << endl;
        continue;
      }
      set<int>::iterator ed = s.end(), st = s.begin(), x = s.find(b);
      ed--;
      if (x == ed) {
        x--;
        ms.insert(b - *x);
      } else if (x == st) {
        x++;
        ms.insert(*x - b);
      } else {
        set<int>::iterator p1 = x, p2 = x;
        p1--, p2++;
        ms.insert(b - *p1);
        ms.insert(*p2 - b);
        multiset<int>::iterator p3 = ms.find(*p2 - *p1);
        ms.erase(p3);
      }
    } else {
      if (s.size() == 1) {
        s.erase(b);
        cout << 0 << endl;
        continue;
      }
      set<int>::iterator p1 = s.find(b), ed = s.end(), st = s.begin(), p2, p3;
      ed--;
      if (p1 == ed) {
        p2 = ed;
        p2--;
        multiset<int>::iterator p4 = ms.find(*ed - *p2);
        ms.erase(p4);
        s.erase(b);
      } else if (p1 == st) {
        p2 = st;
        p2++;
        multiset<int>::iterator p4 = ms.find(*p2 - *st);
        ms.erase(p4);
        s.erase(b);
      } else {
        p2 = p1, p3 = p1;
        p2--, p3++;
        auto p4 = ms.find(*p3 - b);
        ms.erase(p4);
        p4 = ms.find(b - *p2);
        ms.erase(p4);
        ms.insert(*p3 - *p2);
        s.erase(b);
      }
    }
    if (s.size() <= 2)
      cout << 0 << endl;
    else {
      auto p10 = s.begin(), p11 = s.end();
      p11--;
      cout << *p11 - *p10 - *ms.begin() << endl;
    }
  }
  return 0;
}
