#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
void solve() {
  int n, q;
  scanf("%d %d", &n, &q);
  set<long long> s;
  s.insert(-2e9);
  s.insert(2e9 + 7);
  for (int i = 0; i < n; i++) {
    int first;
    scanf("%d", &first);
    s.insert(first);
  }
  multiset<long long> ans;
  int last = *s.begin();
  for (auto it : s) {
    ans.insert(it - last);
    last = it;
  }
  ans.erase(0);
  if (s.size() <= 4) {
    printf("0\n");
  } else
    printf("%lld\n", *prev(prev(s.end())) - *next(s.begin()) -
                         *prev(prev(prev(ans.end()))));
  while (q--) {
    int t, first;
    scanf("%d %d", &t, &first);
    if (t == 1) {
      auto it = s.lower_bound(first);
      auto it2 = prev(it);
      ans.erase(ans.find(*it - *it2));
      ans.insert(*it - first);
      ans.insert(first - *it2);
      s.insert(first);
    } else {
      s.erase(first);
      auto it = s.lower_bound(first);
      auto it2 = prev(it);
      ans.insert(*it - *it2);
      ans.erase(ans.find(*it - first));
      ans.erase(ans.find(first - *it2));
    }
    if (s.size() <= 4) {
      printf("0\n");
    } else
      printf("%lld\n", *prev(prev(s.end())) - *next(s.begin()) -
                           *prev(prev(prev(ans.end()))));
  }
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
}
