#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9 + 7;
int tem[N], va[N], ans;
int num[N << 2], mx[N << 2], mi[N << 2];
void build(int t, int l, int r) {
  mx[t] = 0, mi[t] = inf;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(t << 1, l, mid);
  build(t << 1 | 1, mid + 1, r);
}
void update(int t, int l, int r, int pos, int d) {
  if (l == r) {
    num[t] = d;
    if (num[t])
      mx[t] = mi[t] = tem[l];
    else
      mx[t] = 0, mi[t] = inf;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    update(t << 1, l, mid, pos, d);
  else
    update(t << 1 | 1, mid + 1, r, pos, d);
  num[t] = num[t << 1] + num[t << 1 | 1];
  mi[t] = min(mi[t << 1], mi[t << 1 | 1]);
  mx[t] = max(mx[t << 1], mx[t << 1 | 1]);
}
void query_mi(int t, int l, int r, int ei, int ej) {
  if (ei <= l && r <= ej) {
    ans = min(ans, mi[t]);
    return;
  }
  int mid = (l + r) >> 1;
  if (ei <= mid) query_mi(t << 1, l, mid, ei, ej);
  if (ej > mid) query_mi(t << 1 | 1, mid + 1, r, ei, ej);
}
void query_mx(int t, int l, int r, int ei, int ej) {
  if (ei <= l && r <= ej) {
    ans = max(ans, mx[t]);
    return;
  }
  int mid = (l + r) >> 1;
  if (ei <= mid) query_mx(t << 1, l, mid, ei, ej);
  if (ej > mid) query_mx(t << 1 | 1, mid + 1, r, ei, ej);
}
int st[N << 2];
void modify(int t, int l, int r, int pos, int d) {
  if (l == r) {
    st[t] = d;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(t << 1, l, mid, pos, d);
  else
    modify(t << 1 | 1, mid + 1, r, pos, d);
  st[t] = max(st[t << 1], st[t << 1 | 1]);
}
bool tp[N];
int vb[N];
int main() {
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    cin >> va[i];
    tem[++cnt] = va[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> tp[i] >> vb[i];
    if (tp[i]) tem[++cnt] = vb[i];
  }
  sort(tem + 1, tem + cnt + 1);
  sort(va + 1, va + n + 1);
  int ni = unique(tem + 1, tem + cnt + 1) - tem - 1;
  build(1, 1, ni);
  for (int i = 1; i <= n; i++)
    va[i] = lower_bound(tem + 1, tem + ni + 1, va[i]) - tem;
  for (int i = 1; i <= n; i++) {
    update(1, 1, ni, va[i], 1);
    if (i != n) modify(1, 1, ni, va[i + 1], tem[va[i + 1]] - tem[va[i]]);
  }
  cout << mx[1] - mi[1] - st[1] << endl;
  for (int i = 1; i <= m; i++) {
    int pos = lower_bound(tem + 1, tem + ni + 1, vb[i]) - tem;
    if (tp[i]) {
      ans = 0;
      query_mx(1, 1, ni, 1, pos);
      int a = ans;
      ans = inf;
      query_mi(1, 1, ni, pos, ni);
      int b = ans;
      update(1, 1, ni, pos, 1);
      if (a) modify(1, 1, ni, pos, vb[i] - a);
      if (b != inf) {
        int c = lower_bound(tem + 1, tem + ni + 1, b) - tem;
        modify(1, 1, ni, c, b - vb[i]);
      }
    } else {
      update(1, 1, ni, pos, 0);
      modify(1, 1, ni, pos, 0);
      ans = 0;
      query_mx(1, 1, ni, 1, pos);
      int a = ans;
      ans = inf;
      query_mi(1, 1, ni, pos, ni);
      int b = ans;
      if (b != inf) {
        int c = lower_bound(tem + 1, tem + ni + 1, b) - tem;
        if (a)
          modify(1, 1, ni, c, b - a);
        else
          modify(1, 1, ni, c, 0);
      }
    }
    cout << max(mx[1] - mi[1] - st[1], 0) << endl;
  }
}
