#include <bits/stdc++.h>
using namespace std;
multiset<long long, greater<long long>> mp;
long long answer(set<long long> &v) {
  if ((long long)v.size() <= 2) return 0;
  long long d = *prev(v.end()) - *v.begin();
  return d - *mp.begin();
}
void calc(set<long long> &v) {
  if (v.size() <= 2) {
    cout << 0 << endl;
    return;
  }
  for (auto nxt = next(v.begin()), pre = v.begin(); nxt != v.end();
       ++nxt, ++pre) {
    mp.insert(*nxt - *pre);
  }
  cout << answer(v) << endl;
}
void extra(set<long long> &v, long long val, long long f) {
  if (val) {
    v.insert(f);
    auto it = v.find(f);
    if (it == v.begin()) {
      long long d = *next(it) - f;
      mp.insert(d);
    } else if (it == prev(v.end())) {
      long long d = f - *prev(it);
      mp.insert(d);
    } else {
      long long pre = *prev(it);
      long long nxt = *next(it);
      long long pd = nxt - pre;
      mp.erase(mp.find(pd));
      mp.insert(nxt - f);
      mp.insert(f - pre);
    }
  } else {
    if ((long long)v.size() == 1) {
      v.clear();
      mp.clear();
    } else {
      auto it = v.find(f);
      if (it == v.begin()) {
        long long nxt = *next(it);
        mp.erase(mp.find(nxt - f));
      } else if (it == prev(v.end())) {
        long long pre = *prev(it);
        mp.erase(mp.find(f - pre));
      } else {
        long long nxt = *next(it);
        long long pre = *prev(it);
        mp.erase(mp.find(nxt - f));
        mp.erase(mp.find(f - pre));
        mp.insert(nxt - pre);
      }
      v.erase(f);
    }
  }
  cout << answer(v) << endl;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  long long n, q;
  cin >> n >> q;
  set<long long> st;
  for (long long i = 0; i < n; ++i) {
    long long x;
    cin >> x;
    st.insert(x);
  }
  calc(st);
  while (q--) {
    long long val, f;
    cin >> val >> f;
    extra(st, val, f);
  }
  return 0;
}
