#include <bits/stdc++.h>
using namespace std;
int scan_int() {
  int x;
  if (!scanf("%d", &x)) throw 1;
  return x;
}
int f(const set<int>& B, const multiset<int>& C) {
  if (C.empty()) return 0;
  return *B.rbegin() - *B.begin() - *C.rbegin();
}
int main() {
  int N = scan_int();
  int Q = scan_int();
  vector<int> A(N);
  for (auto& x : A) x = scan_int();
  sort(A.begin(), A.end());
  set<int> B(A.begin(), A.end());
  multiset<int> C;
  for (int i = 1; i < N; ++i) C.insert(A[i] - A[i - 1]);
  printf("%d\n", f(B, C));
  for (int tt = 0; tt < Q; ++tt) {
    int t = scan_int();
    int x = scan_int();
    if (t == 0) {
      if (x == *B.begin()) {
        B.erase(x);
        if (B.size() <= 1) {
          C.clear();
        } else {
          C.erase(C.find(*B.begin() - x));
        }
      } else if (x == *B.rbegin()) {
        B.erase(x);
        if (B.size() <= 1) {
          C.clear();
        } else {
          C.erase(C.find(x - *B.rbegin()));
        }
      } else {
        B.erase(x);
        auto it = B.upper_bound(x);
        int y = *it;
        --it;
        int z = *it;
        C.erase(C.find(y - x));
        C.erase(C.find(x - z));
        C.insert(y - z);
      }
    } else {
      if (B.empty()) {
      } else if (x < *B.begin()) {
        C.insert(*B.begin() - x);
      } else if (x > *B.rbegin()) {
        C.insert(x - *B.rbegin());
      } else {
        auto it = B.upper_bound(x);
        int y = *it;
        --it;
        int z = *it;
        C.erase(C.find(y - z));
        C.insert(y - x);
        C.insert(x - z);
      }
      B.insert(x);
    }
    printf("%d\n", f(B, C));
  }
}
