#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
void solve() {
  long long n, a, q;
  cin >> n >> q;
  set<long long> s;
  multiset<long long> diff;
  vector<long long> v(n);
  long long maxi = 0, mini = INT_MAX;
  for (long long i = 0; i < n; i++) {
    cin >> v[i];
    s.insert(v[i]);
    maxi = max(maxi, v[i]);
    mini = min(mini, v[i]);
  }
  sort(v.begin(), v.end());
  for (long long i = 1; i < n; i++) diff.insert(v[i] - v[i - 1]);
  long long x;
  if (n == 1) {
    cout << 0 << "\n";
  } else {
    cout << maxi - mini - *prev(diff.end()) << endl;
  }
  while (q--) {
    cin >> a >> x;
    if (a == 0) {
      auto it = s.find(x);
      if (s.size() == 1) {
        s.clear();
        cout << 0 << "\n";
        diff.clear();
        continue;
      }
      if (s.size() == 2) {
        s.erase(x);
        diff.clear();
        cout << 0 << "\n";
        continue;
      }
      if (it == s.begin()) {
        diff.erase(diff.find(*next(it) - *it));
      } else if (it == prev(s.end())) {
        diff.erase(diff.find(*it - *prev(it)));
      } else {
        diff.erase(diff.find(*next(it) - *it));
        diff.erase(diff.find(*it - *prev(it)));
        diff.insert(*next(it) - *prev(it));
      }
      s.erase(it);
      cout << *prev(s.end()) - *s.begin() - *prev(diff.end()) << "\n";
    }
    if (a == 1) {
      s.insert(x);
      auto it = s.find(x);
      if (s.size() == 1) {
        cout << 0 << "\n";
        continue;
      }
      if (s.size() == 2) {
        cout << 0 << "\n";
        diff.clear();
        diff.insert(*prev(s.end()) - *s.begin());
        continue;
      }
      if (it == s.begin()) {
        diff.insert(*next(it) - *it);
      } else if (it == prev(s.end())) {
        diff.insert(*it - *prev(it));
      } else {
        diff.erase(diff.find(*next(it) - *prev(it)));
        diff.insert(*it - *prev(it));
        diff.insert(*next(it) - *it);
      }
      cout << *prev(s.end()) - *s.begin() - *prev(diff.end()) << "\n";
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t = 1;
  while (t--) {
    solve();
  }
}
