#include <bits/stdc++.h>
using namespace std;
int n, q;
set<int> p;
multiset<int> mx;
int cnt() {
  if (p.size() <= 1) return 0;
  return *p.rbegin() - *p.begin() - *mx.rbegin();
}
void era(int k) {
  p.erase(k);
  if (!p.size()) return;
  auto nxt = p.lower_bound(k);
  auto pre = nxt;
  if (nxt != p.end()) mx.erase(mx.lower_bound(*nxt - k));
  if (nxt != p.begin()) {
    pre--;
    mx.erase(mx.lower_bound(k - *pre));
    if (nxt != p.end()) mx.insert(*nxt - *pre);
  }
}
void ins(int k) {
  if (!p.size()) {
    p.insert(k);
    return;
  }
  auto nxt = p.lower_bound(k);
  auto pre = nxt;
  if (nxt != p.end()) mx.insert(*nxt - k);
  if (nxt != p.begin()) {
    pre--;
    mx.insert(k - *pre);
    if (nxt != p.end()) mx.erase(mx.lower_bound(*nxt - *pre));
  }
  p.insert(k);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (int i = 0, k; i < n; i++) cin >> k, p.insert(k);
  long long ans = *p.rbegin() - *p.begin();
  for (auto i = p.begin(); i != p.end(); i++)
    ans += *(next(i)) - *i, mx.insert(*(next(i)) - *i);
  cout << cnt() << '\n';
  for (int i = 0, a, b; i < q; i++) {
    cin >> a >> b;
    if (a == 0)
      era(b);
    else
      ins(b);
    cout << cnt() << '\n';
  }
  return 0;
}
