#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * f;
}
int n, a[300100], q;
struct node {
  int x;
  int val;
};
bool operator<(node a, node b) { return a.val < b.val; }
priority_queue<node> heap;
set<int> tree;
int main() {
  n = read(), q = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    tree.insert(a[i]);
  }
  sort(a + 1, a + 1 + n);
  for (int i = 1; i < n; ++i) {
    heap.push({a[i], a[i + 1] - a[i]});
  }
  if (tree.size() <= 2) {
    puts("0");
  } else {
    cout << (*(--tree.end())) - (*tree.begin()) - heap.top().val << endl;
  }
  for (int i = 1; i <= q; ++i) {
    int t = read(), p = read();
    if (t == 0) {
      set<int>::iterator it;
      it = tree.lower_bound(p);
      set<int>::iterator lst = it;
      lst--;
      if (it != tree.end()) {
        set<int>::iterator nxt = it;
        nxt++;
        heap.push({(*lst), (*nxt) - (*lst)});
        tree.erase(it);
      }
    } else {
      tree.insert(p);
      set<int>::iterator it;
      it = tree.lower_bound(p);
      set<int>::iterator nxt = it;
      nxt++;
      set<int>::iterator lst = it;
      lst--;
      heap.push({(*lst), (*it) - (*lst)});
      heap.push({(*it), (*nxt) - (*it)});
    }
    bool flag = false;
    do {
      flag = false;
      int x = heap.top().x, val = heap.top().val;
      set<int>::iterator it;
      it = tree.find(x);
      set<int>::iterator nxt = it;
      if (it != tree.end()) nxt++;
      if (it == tree.end() || nxt == tree.end()) {
        heap.pop();
        flag = true;
      } else {
        if (val != (*nxt) - (*it)) {
          heap.pop();
          flag = true;
        }
      }
    } while (flag && heap.size());
    if (tree.size() <= 2) {
      puts("0");
    } else {
      cout << (*(--tree.end())) - (*tree.begin()) - heap.top().val;
      puts("");
    }
  }
  return 0;
}
