#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int N, Q, P[MAXN], T[MAXN], X[MAXN];
void solve() {
  set<int> s;
  multiset<int> diff;
  for (int i = 0; i < (int)N; ++i) s.insert(P[i]);
  int range = (s.size() >= 2) ? (*prev(s.end()) - *s.begin()) : 0;
  for (auto i = s.begin(); i != prev(s.end()); i++) diff.insert(*next(i) - *i);
  (s.size() <= 2) ? cout << 0 << endl
                  : cout << range - *prev(diff.end()) << endl;
  for (int i = 0; i < (int)Q; ++i) {
    if (T[i] == 0) {
      auto iter = s.find(X[i]);
      if (s.size() == 1) {
      } else if (iter == s.begin() || iter == prev(s.end())) {
        int dif =
            (iter == s.begin()) ? (*next(iter) - *iter) : (*iter - *prev(iter));
        diff.erase(diff.find(dif));
      } else {
        int dif1 = *next(iter) - *iter;
        int dif2 = *iter - *prev(iter);
        diff.erase(diff.find(dif1));
        diff.erase(diff.find(dif2));
        diff.insert(dif1 + dif2);
      }
      s.erase(iter);
    } else {
      s.insert(X[i]);
      auto iter = s.find(X[i]);
      if (s.empty()) {
      } else if (iter == s.begin() || iter == prev(s.end())) {
        int dif =
            (iter == s.begin()) ? (*next(iter) - *iter) : (*iter - *prev(iter));
        diff.insert(dif);
      } else {
        int dif1 = *next(iter) - *iter;
        int dif2 = *iter - *prev(iter);
        diff.erase(diff.find(dif1 + dif2));
        diff.insert(dif1);
        diff.insert(dif2);
      }
    }
    range = (s.size() >= 2) ? (*prev(s.end()) - *s.begin()) : 0;
    (s.size() <= 2) ? cout << 0 << endl
                    : cout << range - *prev(diff.end()) << endl;
  }
}
int main() {
  cin >> N >> Q;
  for (int i = 0; i < (int)N; ++i) cin >> P[i];
  for (int i = 0; i < (int)Q; ++i) cin >> T[i] >> X[i];
  solve();
  return 0;
}
