#include <bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
using namespace std;
const int maxn = 2e6 + 7;
const int INF = 0x3f3f3f3f;
const long long INFF = 1e18;
int a[maxn], n, q, op, x;
set<int> S, T;
map<int, int> M;
set<int>::iterator it;
int pre(int x) {
  it = S.find(x);
  if (it == S.begin())
    return 0;
  else
    return *(--it);
}
int next(int x) {
  it = S.find(x);
  ++it;
  if (it == S.end())
    return 0;
  else
    return *it;
}
void insert_x(int x) {
  S.insert(x);
  int pre_x = pre(x);
  int next_x = next(x);
  if (pre_x) {
    if (M[x - pre_x] == 0) T.insert(x - pre_x);
    M[x - pre_x]++;
  }
  if (next_x) {
    if (M[next_x - x] == 0) T.insert(next_x - x);
    M[next_x - x]++;
  }
  if (pre_x && next_x) {
    if (M[next_x - pre_x] == 1) T.erase(next_x - pre_x);
    M[next_x - pre_x]--;
  }
}
void delete_x(int x) {
  int pre_x = pre(x);
  int next_x = next(x);
  S.erase(x);
  if (pre_x) {
    if (M[x - pre_x] == 1) T.erase(x - pre_x);
    M[x - pre_x]--;
  }
  if (next_x) {
    if (M[next_x - x] == 1) T.erase(next_x - x);
    M[next_x - x]--;
  }
  if (pre_x && next_x) {
    if (M[next_x - pre_x] == 0) T.insert(next_x - pre_x);
    M[next_x - pre_x]++;
  }
}
int query() {
  if (S.size() <= 1) return 0;
  return *S.rbegin() - *S.begin() - *T.rbegin();
}
int main() {
  S.clear();
  T.clear();
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), insert_x(a[i]);
  printf("%d\n", query());
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &op, &x);
    if (op)
      insert_x(x);
    else
      delete_x(x);
    printf("%d\n", query());
  }
  return 0;
}
