#include <bits/stdc++.h>
using namespace std;
using ll = long long;
set<ll> pos;
multiset<ll> diff;
void add(ll x) {
  auto it = pos.insert(x).first;
  if (next(it) != pos.end()) diff.insert(*next(it) - x);
  if (it != pos.begin()) diff.insert(x - *prev(it));
  if (it != pos.begin() && next(it) != pos.end())
    diff.erase(diff.find(*next(it) - *prev(it)));
}
void erase(ll x) {
  auto it = pos.find(x);
  if (next(it) != pos.end()) diff.erase(diff.find(*next(it) - x));
  if (it != pos.begin()) diff.erase(diff.find(x - *prev(it)));
  if (it != pos.begin() && next(it) != pos.end())
    diff.insert(*next(it) - *prev(it));
  pos.erase(it);
}
ll query() {
  if (pos.size() <= 2) return 0;
  return *pos.rbegin() - *pos.begin() - *diff.rbegin();
}
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N, Q;
  cin >> N >> Q;
  for (int i = 0; i < N; ++i) {
    ll x;
    cin >> x;
    add(x);
  }
  cout << query() << '\n';
  for (int i = 0; i < Q; ++i) {
    ll q, x;
    cin >> q >> x;
    if (q == 0)
      erase(x);
    else
      add(x);
    cout << query() << '\n';
  }
  return 0;
}
