#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int getans(set<int>& S, priority_queue<pii>& gaps) {
  if (gaps.empty()) return 0;
  return *S.rbegin() - *S.begin() - gaps.top().first;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, q;
  cin >> n >> q;
  set<int> S;
  for (int i = 0; i < n; i++) {
    int t;
    cin >> t;
    S.insert(t);
  }
  priority_queue<pii> gaps;
  for (auto it = S.begin(); it != S.end(); it++) {
    if (it == S.begin()) continue;
    auto last = it;
    last--;
    gaps.push({*it - *last, *it});
  }
  cout << getans(S, gaps) << '\n';
  for (int qn = 0; qn < q; qn++) {
    int cmd, t;
    cin >> cmd >> t;
    if (cmd == 1) {
      S.insert(t);
      auto it = S.find(t);
      auto next = it;
      next++;
      if (next != S.end()) {
        gaps.push({(*next - *it), *next});
      }
      if (it != S.begin()) {
        auto last = it;
        last--;
        gaps.push({(*it - *last), *it});
      }
    } else {
      auto it = S.find(t);
      auto next = it;
      next++;
      if (next != S.end() && it != S.begin()) {
        auto last = it;
        last--;
        gaps.push({(*next - *last), *next});
      }
      S.erase(t);
    }
    while (1) {
      if (gaps.empty()) break;
      int p1 = gaps.top().second;
      int p2 = gaps.top().second - gaps.top().first;
      if (S.find(p1) != S.end() && S.find(p2) != S.end()) {
        auto pp1 = S.find(p1);
        auto pp2 = S.find(p2);
        auto pp3 = pp1;
        pp3--;
        if (pp2 == pp3) break;
      }
      gaps.pop();
    }
    cout << getans(S, gaps) << '\n';
  }
}
