#include <bits/stdc++.h>
using namespace std;
int n, q, a[200006];
multiset<int>::iterator it;
multiset<int> SS, s;
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    s.insert(a[i]);
  }
  sort(a + 1, a + 1 + n);
  for (int i = 2; i <= n; i++) SS.insert(a[i] - a[i - 1]);
  int big, sm, mi, cnt = 0;
  it = s.begin();
  while (it != s.end() && cnt <= 2) {
    it++;
    cnt++;
  }
  if (cnt <= 2) {
    printf("0\n");
  } else {
    it = s.end();
    it--;
    big = *it;
    it = s.begin();
    sm = *it;
    it = SS.end();
    it--;
    mi = *it;
    printf("%d\n", big - sm - mi);
  }
  int typ, num;
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &typ, &num);
    if (typ) {
      int suf, pre;
      it = s.lower_bound(num);
      if (it == s.end()) {
        if (!s.empty()) {
          it--;
          SS.insert(num - *it);
        }
      } else {
        suf = *it;
        if (it == s.begin()) {
          SS.insert(*it - num);
        } else {
          it--;
          pre = *it;
          it = SS.lower_bound(suf - pre);
          SS.erase(it);
          SS.insert(suf - num);
          SS.insert(num - pre);
        }
      }
      s.insert(num);
    } else {
      int suf, pre;
      it = s.lower_bound(num);
      it++;
      if (it == s.end()) {
        it--;
        if (it == s.begin())
          ;
        else {
          it--;
          pre = *it;
          it = SS.lower_bound(num - pre);
          SS.erase(it);
        }
      } else {
        suf = *it;
        it--;
        if (it == s.begin()) {
          it = SS.lower_bound(suf - num);
          SS.erase(it);
        } else {
          it--;
          pre = *it;
          it = SS.lower_bound(num - pre);
          SS.erase(it);
          it = SS.lower_bound(suf - num);
          SS.erase(it);
          SS.insert(suf - pre);
        }
      }
      s.erase(num);
    }
    cnt = 0;
    it = s.begin();
    while (it != s.end() && cnt <= 2) {
      it++;
      cnt++;
    }
    if (cnt <= 2) {
      printf("0\n");
    } else {
      it = s.end();
      it--;
      big = *it;
      it = s.begin();
      sm = *it;
      it = SS.end();
      it--;
      mi = *it;
      printf("%d\n", big - sm - mi);
    }
  }
  return 0;
}
