#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using namespace std;
template <typename T>
inline bool read(T &ret) {
  T x = 0, f = 1;
  char ch = getchar();
  while (ch != EOF && (ch > '9' || ch < '0')) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  if (EOF == ch) return false;
  do x = x * 10 + ch - 48, ch = getchar();
  while (ch >= '0' && ch <= '9');
  ret = x * f;
  return true;
}
inline char nc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
template <typename T>
bool rn(T &v) {
  static char ch;
  while (ch != EOF && !isdigit(ch)) ch = nc();
  if (ch == EOF) return false;
  for (v = 0; isdigit(ch); ch = nc()) v = v * 10 + ch - '0';
  return true;
}
template <typename T>
void o(T p) {
  static int stk[70], tp;
  if (p == 0) {
    putchar('0');
    return;
  }
  if (p < 0) {
    p = -p;
    putchar('-');
  }
  while (p) stk[++tp] = p % 10, p /= 10;
  while (tp) putchar(stk[tp--] + '0');
}
LL bin(LL x, LL n, LL MOD) {
  LL ret = MOD != 1;
  for (x %= MOD; n; n >>= 1, x = x * x % MOD)
    if (n & 1) ret = ret * x % MOD;
  return ret;
}
inline LL get_inv(LL x, LL p) { return bin(x, p - 2, p); }
const int MAXN = 1e5 + 10;
int n, q;
void Solve() {
  cin >> n >> q;
  set<int> positions;
  multiset<int> gaps;
  auto &&add_position = [&](int p) {
    auto it = positions.insert(p).first;
    if (next(it) != positions.end()) {
      gaps.insert(*next(it) - p);
    }
    if (it != positions.begin()) {
      gaps.insert(p - *prev(it));
      if (next(it) != positions.end()) {
        gaps.erase(gaps.find(*next(it) - *prev(it)));
      }
    }
  };
  auto &&erase_position = [&](int p) {
    auto it = positions.find(p);
    if (next(it) != positions.end()) {
      gaps.erase(gaps.find(*next(it) - p));
    }
    if (it != positions.begin()) {
      gaps.erase(gaps.find(p - *prev(it)));
      if (next(it) != positions.end()) {
        gaps.insert(*next(it) - *prev(it));
      }
    }
    positions.erase(it);
  };
  auto &&query = [&] {
    if (positions.size() <= 2) return 0;
    return *(--positions.end()) - *positions.begin() - *(--gaps.end());
  };
  for (int i = 0; i < n; i++) {
    int p;
    cin >> p;
    add_position(p);
  }
  cout << query() << endl;
  for (int i = 0; i < q; i++) {
    int a, b;
    cin >> a >> b;
    if (a == 0) {
      erase_position(b);
    } else {
      add_position(b);
    }
    cout << query() << endl;
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  Solve();
  return 0;
  return 0;
}
