#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 7;
void add(int p, set<int> &sx, multiset<int> &msx) {
  sx.insert(p);
  auto it = sx.find(p);
  int prv = -1, nxt = -1;
  if (it != sx.begin()) {
    --it;
    msx.insert(p - *it);
    prv = *it;
    ++it;
  }
  ++it;
  if (it != sx.end()) {
    msx.insert(*it - p);
    nxt = *it;
  }
  if (prv != -1 && nxt != -1) msx.erase(msx.find(nxt - prv));
}
void rem(int p, set<int> &sx, multiset<int> &msx) {
  auto it = sx.find(p);
  int prv = -1, nxt = -1;
  if (it != sx.begin()) {
    --it;
    msx.erase(msx.find(p - *it));
    prv = *it;
    ++it;
  }
  ++it;
  if (it != sx.end()) {
    msx.erase(msx.find(*it - p));
    nxt = *it;
  }
  sx.erase(p);
  if (prv != -1 && nxt != -1) msx.insert(nxt - prv);
}
int get(set<int> &sx, multiset<int> &msx) {
  if (sx.size() <= 2) return 0;
  return *sx.rbegin() - *sx.begin() - *msx.rbegin();
}
void solve() {
  int n, q;
  cin >> n >> q;
  set<int> sx;
  multiset<int> msx;
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    add(k, sx, msx);
  }
  cout << get(sx, msx) << "\n";
  while (q--) {
    int t, p;
    cin >> t >> p;
    if (t == 0)
      rem(p, sx, msx);
    else
      add(p, sx, msx);
    cout << get(sx, msx) << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
