#include <bits/stdc++.h>
using namespace std;
set<int> s;
multiset<int> dif;
map<int, pair<int, int>> mp;
int main() {
  std::ios_base::sync_with_stdio(0), cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    s.insert(a[i]);
  }
  sort(a.begin(), a.end());
  for (int i = 0; i < n; ++i) {
    if (i)
      mp[a[i]].first = a[i - 1];
    else
      mp[a[i]].first = -1;
    if (i != n - 1)
      mp[a[i]].second = a[i + 1], dif.insert(a[i + 1] - a[i]);
    else
      mp[a[i]].second = -1;
  }
  if (s.size() <= 2)
    cout << 0 << '\n';
  else
    cout << *(s.rbegin()) - *s.begin() - *dif.rbegin() << '\n';
  while (q--) {
    int c, x;
    cin >> c >> x;
    if (c == 0) {
      int t1 = mp[x].first, t2 = mp[x].second;
      s.erase(x);
      if (t1 != -1) dif.erase(dif.find(x - t1)), mp[t1].second = -1;
      if (t2 != -1) dif.erase(dif.find(t2 - x)), mp[t2].first = -1;
      if (t1 != -1 && t2 != -1)
        mp[t1].second = t2, mp[t2].first = t1, dif.insert(t2 - t1);
      mp.erase(x);
    } else {
      if (s.empty()) {
        s.insert(x);
        cout << 0 << '\n';
        mp[x] = {-1, -1};
        continue;
      }
      auto it = s.lower_bound(x);
      if (it != s.end()) {
        if (it != s.begin()) {
          int t2 = *it;
          int t1 = mp[t2].first;
          mp[t1].second = x;
          mp[t2].first = x;
          mp[x] = {t1, t2};
          dif.erase(dif.find(t2 - t1));
          dif.insert(x - t1);
          dif.insert(t2 - x);
          s.insert(x);
        } else {
          int t2 = *s.begin();
          mp[t2].first = x;
          mp[x] = {-1, t2};
          dif.insert(t2 - x);
          s.insert(x);
        }
      } else {
        int t1 = *s.rbegin();
        mp[t1].second = x;
        mp[x] = {t1, -1};
        dif.insert(x - t1);
        s.insert(x);
      }
    }
    if (s.size() <= 2)
      cout << 0 << '\n';
    else
      cout << *(s.rbegin()) - *s.begin() - *dif.rbegin() << '\n';
  }
  return 0;
}
