#include <bits/stdc++.h>
using namespace std;
int a[100001], tot;
int n, m;
set<int> st;
multiset<int> q;
void pr() {
  if (tot <= 2) {
    puts("0");
    return;
  }
  int ans = (*--st.end()) - (*st.begin()) - (*--q.end());
  printf("%d\n", ans);
}
void add(int x) {
  if (tot == 0) {
    st.insert(x);
    tot++;
    return;
  }
  if (tot == 1) {
    st.insert(x);
    q.insert((*--st.end()) - (*st.begin()));
    tot++;
    return;
  }
  if (x < (*st.begin()))
    q.insert((*st.begin()) - x);
  else if (x > (*--st.end()))
    q.insert(x - (*--st.end()));
  else {
    auto it = st.lower_bound(x);
    int R = *it, L = *--it;
    q.erase(q.find(R - L));
    q.insert(x - L), q.insert(R - x);
  }
  st.insert(x);
  tot++;
}
void del(int x) {
  if (tot == 1) {
    st.erase(x);
    tot--;
    return;
  }
  if (x == (*st.begin()))
    q.erase(q.find((*++st.begin()) - x));
  else if (x == (*--st.end()))
    q.erase(q.find((*--st.end()) - (*-- --st.end())));
  else {
    auto it = st.find(x);
    int L = *--it, R = *++ ++it;
    q.erase(q.find(R - x));
    q.erase(q.find(x - L));
    q.insert(R - L);
  }
  st.erase(x);
  tot--;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  sort(a + 1, a + n + 1);
  st.insert(a[1]);
  for (int i = 1; i < n; i++) q.insert(a[i + 1] - a[i]), st.insert(a[i + 1]);
  tot = n;
  pr();
  for (int i = 1; i <= m; i++) {
    int t, x;
    scanf("%d%d", &t, &x);
    if (t == 0)
      del(x);
    else
      add(x);
    pr();
  }
}
