#include <bits/stdc++.h>
using namespace std;
const long long inf = 8e18;
const long long maxn = 2e5 + 10;
const long long mod = 1e9 + 7;
long long n, a[maxn], q, op, x;
set<long long> st1;
multiset<long long> st2;
template <class T>
void read(T &x) {
  T res = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    res = (res << 3) + (res << 1) + c - '0';
    c = getchar();
  }
  x = res * f;
}
long long solve() {
  set<long long>::iterator pos1 = st1.begin(), pos2 = --st1.end();
  multiset<long long>::iterator pos = --st2.end();
  return *pos2 - *pos1 - *pos;
}
void Delete() {
  set<long long>::iterator pos, pos1, pos2;
  pos = st1.find(x);
  pos1 = pos2 = pos;
  if (pos != st1.begin()) pos1--;
  if (pos != --st1.end()) pos2++;
  if (pos != st1.begin()) st2.erase(st2.find(*pos - *pos1));
  if (pos != --st1.end()) st2.erase(st2.find(*pos2 - *pos));
  if (pos != --st1.end() && pos != st1.begin()) st2.insert(*pos2 - *pos1);
  st1.erase(x);
}
void Insert() {
  st1.insert(x);
  set<long long>::iterator pos, pos1, pos2;
  pos = st1.find(x);
  pos1 = pos2 = pos;
  if (pos != st1.begin()) pos1--;
  if (pos != --st1.end()) pos2++;
  if (pos != st1.begin()) st2.insert(*pos - *pos1);
  if (pos != --st1.end()) st2.insert(*pos2 - *pos);
  if (pos != --st1.end() && pos != st1.begin())
    st2.erase(st2.find(*pos2 - *pos1));
}
int main() {
  int T = 1;
  while (T--) {
    read(n), read(q);
    for (long long i = 1; i <= n; i++) read(a[i]);
    sort(a + 1, a + 1 + n, less<long long>());
    st1.insert(a[1]);
    for (long long i = 2; i <= n; i++)
      st1.insert(a[i]), st2.insert(a[i] - a[i - 1]);
    if (st1.size() <= 2)
      puts("0");
    else
      printf("%lld\n", solve());
    while (q--) {
      read(op), read(x);
      if (op == 0)
        Delete();
      else
        Insert();
      if (st1.size() <= 2)
        puts("0");
      else
        printf("%lld\n", solve());
    }
  }
  return 0;
}
