#include <bits/stdc++.h>
const int N = (int)1e5 + 7;
const int MOD = (int)1e9 + 7;
const long long INF = (long long)1e18;
using namespace std;
void add(set<long long> &S, multiset<long long> &M, long long x) {
  auto it = S.lower_bound(x);
  long long prev = LLONG_MIN, next = LLONG_MIN;
  if (it != S.end()) {
    next = *it;
  }
  if (it != S.begin()) {
    prev = *(--it);
  }
  if (prev != LLONG_MIN && next != LLONG_MIN) {
    M.erase(M.find(next - prev));
  }
  if (prev != LLONG_MIN) {
    M.insert(x - prev);
  }
  if (next != LLONG_MIN) {
    M.insert(next - x);
  }
  S.insert(x);
}
void remove(set<long long> &S, multiset<long long> &M, long long x) {
  auto it = S.find(x);
  long long prev = LLONG_MIN, next = LLONG_MIN;
  if (it != S.begin()) {
    prev = *(--it);
    it++;
    M.erase(M.find(x - prev));
  }
  it++;
  if (it != S.end()) {
    next = *it;
    M.erase(M.find(next - x));
  }
  S.erase(x);
  if (prev != LLONG_MIN && next != LLONG_MIN) {
    M.insert(next - prev);
  }
}
long long getAns(set<long long> &S, multiset<long long> &M) {
  if (S.size() <= 2) return 0;
  long long mini = *S.begin(), maxi = *S.rbegin(), gap = *M.rbegin();
  return maxi - mini - gap;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  while (t--) {
    long long n, q;
    cin >> n >> q;
    vector<long long> A(n);
    for (int i = 0; i < n; i++) cin >> A[i];
    set<long long> S(A.begin(), A.end());
    multiset<long long> M;
    sort(A.begin(), A.end());
    for (int i = 0; i < n - 1; i++) {
      M.insert(A[i + 1] - A[i]);
    }
    cout << getAns(S, M) << '\n';
    while (q--) {
      long long c, x;
      cin >> c >> x;
      if (c) {
        add(S, M, x);
      } else {
        remove(S, M, x);
      }
      cout << getAns(S, M) << '\n';
    }
  }
  return 0;
}
