#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int p[maxn];
int op[maxn], x[maxn];
unordered_map<int, int> mp;
int mx[maxn << 3];
int lid[maxn << 3], rid[maxn << 3];
vector<int> fuck;
void Merge(int id) {
  mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
  lid[id] = lid[id << 1] ? lid[id << 1] : lid[id << 1 | 1];
  rid[id] = rid[id << 1 | 1] ? rid[id << 1 | 1] : rid[id << 1];
  if (rid[id << 1] && lid[id << 1 | 1]) {
    mx[id] = max(mx[id], fuck[lid[id << 1 | 1]] - fuck[rid[id << 1]]);
  }
}
void Updata(int id, int l, int r, int w, int v) {
  if (l == r) {
    mx[id] = 0;
    lid[id] = rid[id] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (w <= mid)
    Updata(id << 1, l, mid, w, v);
  else
    Updata(id << 1 | 1, mid + 1, r, w, v);
  Merge(id);
}
void PrintOne() {
  if (mx[1] == 0) {
    printf("0\n");
  } else {
    printf("%d\n", fuck[rid[1]] - fuck[lid[1]] - mx[1]);
  }
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  fuck.clear();
  fuck.push_back(-1);
  for (int i = 1; i <= n; i++) {
    scanf("%d", p + i);
    fuck.push_back(p[i]);
  }
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", op + i, x + i);
    fuck.push_back(x[i]);
  }
  sort(fuck.begin(), fuck.end());
  for (int i = 1; i < fuck.size(); i++) {
    mp[fuck[i]] = i;
  }
  memset(lid, 0, sizeof(lid));
  memset(rid, 0, sizeof(rid));
  memset(mx, 0, sizeof(mx));
  int tot = fuck.size() - 1;
  for (int i = 1; i <= n; i++) {
    Updata(1, 1, tot, mp[p[i]], mp[p[i]]);
  }
  PrintOne();
  for (int i = 1; i <= q; i++) {
    Updata(1, 1, tot, mp[x[i]], op[i] * mp[x[i]]);
    PrintOne();
  }
  return 0;
}
