#include <bits/stdc++.h>
using namespace std;
const int Inf = 1e9 + 7;
const int N = 200004;
int bit[N], a[N];
int type[N], pos[N];
int reel[N];
int idx = 0;
void update(int x, int val) {
  while (x < N) {
    bit[x] += val;
    x += x & -x;
  }
}
int query(int x) {
  int ans = 0;
  while (x > 0) {
    ans = ans + bit[x];
    x -= x & -x;
  }
  return ans;
}
int get(int pos) {
  int l = 1, r = idx;
  int ans = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    int val = query(mid);
    if (val >= pos) {
      ans = mid;
      r = mid - 1;
    } else
      l = mid + 1;
  }
  return reel[ans];
}
multiset<int> st;
set<int> st1;
int fun(int mn, int mx, int cnt) {
  if (cnt <= 2) return 0;
  int maxd = *st.rbegin();
  return mx - mn - maxd;
}
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  map<int, int> mp;
  int mn = 1e9 + 7, mx = 0;
  int i;
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    mp[a[i]] = 1;
    st1.insert(a[i]);
  }
  for (i = 1; i <= q; i++) {
    scanf("%d %d", &type[i], &pos[i]);
    mp[pos[i]] = 1;
  }
  map<int, int>::iterator it;
  for (it = mp.begin(); it != mp.end(); it++) {
    idx++;
    mp[it->first] = idx;
    reel[idx] = it->first;
  }
  sort(a + 1, a + n + 1);
  for (i = 1; i <= n; i++) update(mp[a[i]], 1);
  for (i = 2; i <= n; i++) st.insert(a[i] - a[i - 1]);
  int cnt = n;
  mn = *st1.begin();
  mx = *st1.rbegin();
  int maxd;
  if (n == 1)
    maxd = 0;
  else
    maxd = *st.rbegin();
  int ans = mx - mn - maxd;
  printf("%d\n", ans);
  for (i = 1; i <= q; i++) {
    if (type[i] == 0) {
      int indexx = mp[pos[i]];
      int px = query(indexx);
      int val1 = 0, val2 = 0;
      if (px == 1) {
        if (cnt > 1) {
          val1 = get(px + 1);
          st.erase(st.find(val1 - pos[i]));
        }
      } else if (px == cnt) {
        if (cnt > 1) {
          val1 = get(px - 1);
          st.erase(st.find(pos[i] - val1));
        }
      } else {
        val1 = get(px - 1);
        st.erase(st.find(pos[i] - val1));
        val2 = get(px + 1);
        st.erase(st.find(val2 - pos[i]));
        st.insert(val2 - val1);
      }
      cnt--;
      st1.erase(pos[i]);
      update(mp[pos[i]], -1);
      if (cnt == 0)
        ans = 0;
      else
        ans = fun(*st1.begin(), *st1.rbegin(), cnt);
    } else {
      cnt++;
      st1.insert(pos[i]);
      update(mp[pos[i]], 1);
      int indexx = mp[pos[i]];
      int px = query(indexx);
      int val1 = 0, val2 = 0;
      if (px == 1) {
        if (cnt > 1) {
          val1 = get(px + 1);
          st.insert(val1 - pos[i]);
        }
      } else if (px == cnt) {
        if (cnt > 1) {
          val1 = get(px - 1);
          st.insert(pos[i] - val1);
        }
      } else {
        val1 = get(px - 1);
        st.insert(pos[i] - val1);
        val2 = get(px + 1);
        st.insert(val2 - pos[i]);
        st.erase(st.find(val2 - val1));
      }
      ans = fun(*st1.begin(), *st1.rbegin(), cnt);
    }
    printf("%d\n", ans);
  }
  return 0;
}
