#include <bits/stdc++.h>
using namespace std;
void blowback() {
  long long i, j, l, k, d, q, n, x, p, y, m, ans = 0;
  string s, t;
  cin >> n >> q;
  multiset<long long> a;
  for (i = 0; i < n; i++) {
    cin >> j;
    a.insert(j);
  }
  multiset<long long> b;
  auto it = a.begin();
  it++;
  auto it1 = a.begin();
  for (; it != a.end(); it1++, it++) {
    b.insert(*it - *it1);
  }
  if (b.empty()) {
    cout << 0 << "\n";
  } else {
    auto it3 = b.end();
    it3--;
    ans = (*it1 - *a.begin() + 1) - (*it3 + 1);
    cout << ans << "\n";
  }
  for (i = 0; i < q; i++) {
    cin >> j >> k;
    if (j == 1) {
      if (a.size() == 0) {
        a.insert(k);
        cout << 0 << "\n";
        continue;
      }
      auto it4 = a.lower_bound(k);
      auto it5 = it4;
      if (it4 == a.end()) {
        it4--;
        b.insert(k - *it4);
      } else if (it4 == a.begin()) {
        b.insert(*it4 - k);
      } else {
        it5--;
        auto it6 = b.lower_bound(*it4 - *it5);
        b.erase(it6);
        b.insert(*it4 - k);
        b.insert(k - *it5);
      }
      a.insert(k);
    } else {
      auto it4 = a.lower_bound(k);
      auto it5 = it4;
      it5++;
      auto it6 = it4;
      it6--;
      if (it5 != a.end()) {
        auto t1 = b.lower_bound(*it5 - *it4);
        b.erase(t1);
      }
      if (it4 != a.begin()) {
        auto t1 = b.lower_bound(*it4 - *it6);
        b.erase(t1);
      }
      if (it4 != a.begin() && it5 != a.end()) {
        b.insert(*it5 - *it6);
      }
      a.erase(it4);
    }
    if (b.empty()) {
      {
        cout << 0 << "\n";
        continue;
      }
    }
    it1 = a.end();
    it1--;
    auto it3 = b.end();
    it3--;
    ans = (*it1 - *a.begin() + 1) - (*it3 + 1);
    cout << ans << "\n";
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int t = 1;
  while (t--) {
    blowback();
  }
  return 0;
}
