#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
int get(set<int>& s, multiset<int>& len) {
  if (len.empty() == true)
    return 0;
  else {
    return (*s.rbegin() - *s.begin() - *len.rbegin());
  }
}
void add(int pos, set<int>& s, multiset<int>& len) {
  s.insert(pos);
  auto it = s.find(pos);
  bool pre = false, next = false;
  auto itp = it;
  if (it != s.begin()) {
    itp--;
    len.insert(*it - *itp);
    pre = true;
  }
  auto itn = it;
  itn++;
  if (itn != s.end()) {
    len.insert(*itn - *it);
    next = true;
  }
  if (pre and next) {
    len.erase(len.find(*itn - *itp));
  }
}
void rem(int pos, set<int>& s, multiset<int>& len) {
  auto it = s.find(pos);
  auto itp = it, itn = it;
  bool pre = false, next = false;
  if (it != s.begin()) {
    itp--;
    len.erase(len.find(*it - *itp));
    pre = true;
  }
  itn++;
  if (itn != s.end()) {
    len.erase(len.find(*itn - *it));
    next = true;
  }
  if (pre and next) {
    len.insert(*itn - *itp);
  }
  s.erase(pos);
}
void solve() {
  int n, q;
  cin >> n >> q;
  set<int> s;
  multiset<int> len;
  for (int i = 0; i < n; ++i) {
    int pos;
    cin >> pos;
    add(pos, s, len);
  }
  cout << get(s, len) << '\n';
  for (int i = 0; i < q; ++i) {
    int op, pos;
    cin >> op >> pos;
    if (op) {
      add(pos, s, len);
    } else {
      rem(pos, s, len);
    }
    cout << get(s, len) << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  for (int i = 1; i <= t; ++i) {
    solve();
  }
}
