#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &res) {
  char c;
  T flag = 1;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') flag = -1;
  res = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - '0';
  res *= flag;
}
void wenjian() {
  freopen("concatenation.in", "r", stdin);
  freopen("concatenation.out", "w", stdout);
}
void tempwj() {
  freopen("hash.in", "r", stdin);
  freopen("hash.out", "w", stdout);
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long qpow(long long a, long long b, long long mod) {
  a %= mod;
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}
struct chongzai {
  int c;
  bool operator<(const chongzai &b) const { return c > b.c; }
} s;
const int maxn = 1e6 + 177;
const long long mod = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
map<int, int> ma;
priority_queue<int> qu;
set<int> se;
int a[maxn];
int getans() {
  while (qu.size() && ma[qu.top()]) {
    ma[qu.top()]--;
    qu.pop();
  }
  if (se.size() <= 2 || !qu.size()) {
    return 0;
  }
  set<int>::iterator index = se.begin();
  int be = *index;
  index = se.end();
  index--;
  int en = *index;
  return en - be - qu.top();
}
void deal1(int x) {
  if (se.size() == 0) {
    se.insert(x);
    return;
  }
  set<int>::iterator index1 = se.lower_bound(x);
  set<int>::iterator index2 = index1;
  if (index1 == se.end()) {
    int nowl = *(--se.end());
    qu.push(x - nowl);
    se.insert(x);
    return;
  }
  if (index2 == se.begin()) {
    int nowr = *(se.begin());
    qu.push(nowr - x);
    se.insert(x);
    return;
  }
  index1--;
  int be = *index1;
  int en = *index2;
  ma[en - be]++;
  qu.push(x - be);
  qu.push(en - x);
  se.insert(x);
}
void deal2(int x) {
  set<int>::iterator index = se.lower_bound(x);
  set<int>::iterator tot = index;
  set<int>::iterator indexl = --index;
  index = tot;
  set<int>::iterator indexr = ++index;
  index = tot;
  if (index == se.begin()) {
    if (indexr == se.end()) {
      se.erase(x);
      return;
    }
    int en = *indexr;
    ma[en - x]++;
    se.erase(x);
    return;
  }
  if (indexr == se.end()) {
    se.erase(x);
    int en = *indexl;
    ma[x - en]++;
    return;
  }
  int be = *indexl;
  int en = *indexr;
  ma[x - be]++;
  ma[en - x]++;
  se.erase(x);
  qu.push(en - be);
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; i++) {
    se.insert(a[i]);
    if (i > 1) {
      qu.push(a[i] - a[i - 1]);
    }
  }
  printf("%d\n", getans());
  while (q--) {
    int op, index;
    scanf("%d%d", &op, &index);
    if (op) {
      deal1(index);
    } else {
      deal2(index);
    }
    printf("%d\n", getans());
  }
}
