#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const long long INF = 1e9 + 10;
const int MOD = 1e9 + 7;
multiset<int> rub, segs;
void insert(int x) {
  if (rub.size() == 1) {
    int st = *rub.begin();
    segs.insert(abs(x - st));
    rub.insert(x);
    return;
  }
  if (rub.size() == 0) {
    rub.insert(x);
    return;
  }
  auto u = rub.lower_bound(x);
  if (u == rub.end()) {
    int en = *rub.rbegin();
    segs.insert(x - en);
    rub.insert(x);
    return;
  }
  if (u == rub.begin()) {
    int st = *rub.begin();
    segs.insert(st - x);
    rub.insert(x);
    return;
  }
  int en = *u;
  u--;
  int st = *u;
  segs.erase(segs.find(en - st));
  segs.insert(x - st);
  segs.insert(en - x);
  rub.insert(x);
}
int get_ans() {
  if (rub.size() <= 2) return 0;
  int st = *rub.begin(), en = *rub.rbegin();
  int s = *segs.rbegin();
  return en - st - s;
}
void erase(int x) {
  if (rub.size() <= 2) {
    segs.clear();
    rub.erase(x);
    return;
  }
  auto u = rub.upper_bound(x);
  if (u == rub.end()) {
    rub.erase(x);
    int en = *rub.rbegin();
    segs.erase(segs.find(x - en));
    return;
  }
  int en = *u;
  u--;
  if (u == rub.begin()) {
    rub.erase(x);
    int st = *rub.begin();
    segs.erase(segs.find(st - x));
    return;
  }
  u--;
  int st = *u;
  rub.erase(x);
  segs.erase(segs.find(x - st));
  segs.erase(segs.find(en - x));
  segs.insert(en - st);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    insert(x);
  }
  cout << get_ans() << '\n';
  while (q--) {
    int c, x;
    cin >> c >> x;
    if (c == 0)
      erase(x);
    else
      insert(x);
    cout << get_ans() << '\n';
  }
}
