#include <bits/stdc++.h>
using namespace std;
int val[200005], query[200005], w[200005];
map<int, int> mp;
priority_queue<int> pq;
struct BIT {
  int tree[400005] =
      {
          0,
  },
      N;
  void upd(int p, int d) {
    for (p++; p <= N + 1; p += (p & -p)) tree[p] += d;
  }
  int sum(int p) {
    int a = 0;
    for (p++; p > 0; p -= (p & -p)) a += tree[p];
    return a;
  }
} bit;
int loc(int s) {
  int bot, mid, top;
  bot = 1;
  top = bit.N;
  if (s > bit.sum(bit.N)) return bit.N + 1;
  if (s <= 0) return 0;
  while (bot + 1 < top) {
    mid = (bot + top + 1) / 2;
    if (bit.sum(mid) >= s)
      top = mid;
    else
      bot = mid;
  }
  if (bit.sum(bot) == s) return bot;
  return top;
}
void upd(int m, int p) {
  int a, b, c, i, j, k, l, r;
  if (m == 0) {
    l = loc(bit.sum(p) - 1);
    r = loc(bit.sum(p) + 1);
    if (l && r <= bit.N) {
      mp[w[r] - w[l]]++;
      pq.push(w[r] - w[l]);
    }
    if (l) mp[w[p] - w[l]]--;
    if (r <= bit.N) mp[w[r] - w[p]]--;
    bit.upd(p, -1);
  } else {
    l = loc(bit.sum(p));
    r = loc(bit.sum(p) + 1);
    if (l && r <= bit.N) mp[w[r] - w[l]]--;
    if (l) {
      mp[w[p] - w[l]]++;
      pq.push(w[p] - w[l]);
    }
    if (r <= bit.N) {
      mp[w[r] - w[p]]++;
      pq.push(w[r] - w[p]);
    }
    bit.upd(p, 1);
  }
}
void fin() {
  int n = bit.sum(bit.N);
  if (n <= 2) {
    printf("0\n");
    return;
  }
  while (pq.size() && mp[pq.top()] == 0) pq.pop();
  printf("%d\n", w[loc(n)] - w[loc(1)] - pq.top());
}
void solve() {
  int i, j, k, a, b, c, n, q, cnt;
  vector<pair<int, int> > vec;
  scanf("%d%d", &n, &q);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a);
    vec.push_back({a, i});
  }
  for (i = 1; i <= q; i++) {
    scanf("%d%d", &j, &a);
    vec.push_back({a, i + n});
    query[i] = j;
  }
  sort(vec.begin(), vec.end());
  cnt = 1;
  for (i = 1; i <= n + q; i++) {
    if (i > 1 && vec[i - 2].first != vec[i - 1].first) cnt++;
    val[vec[i - 1].second] = cnt;
    w[cnt] = vec[i - 1].first;
  }
  bit.N = cnt;
  for (i = 1; i <= n; i++) {
    upd(1, val[i]);
  }
  fin();
  for (i = 1; i <= q; i++) {
    upd(query[i], val[n + i]);
    fin();
  }
}
int main() {
  int T = 1;
  while (T--) {
    solve();
  }
}
