#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int inf = 1e9;
const int mo = 998244353;
multiset<int> coord, seg;
void update(int x) {
  auto pos = coord.lower_bound(x);
  if (pos == coord.begin()) {
    seg.insert(*pos - x);
  } else if (pos == coord.end()) {
    seg.insert(x - *(--pos));
  } else {
    auto r = pos, l = --pos;
    seg.erase(seg.find(*r - *l));
    seg.insert(*r - x);
    seg.insert(x - *l);
  }
  coord.insert(x);
}
int main() {
  int t = 1;
  while (t--) {
    coord.clear();
    seg.clear();
    int n, q;
    cin >> n >> q;
    for (auto i = (1); i <= (n); ++i) {
      int x;
      cin >> x;
      update(x);
    }
    int ans;
    if (coord.size() > 2)
      ans = *coord.rbegin() - *coord.begin() - *seg.rbegin();
    else
      ans = 0;
    cout << ans << endl;
    for (auto i = (1); i <= (q); ++i) {
      int op, x;
      cin >> op >> x;
      if (op) {
        update(x);
      } else {
        auto pos = coord.lower_bound(x);
        auto r = coord.end();
        r--;
        int tmp;
        if (pos != coord.begin()) {
          auto l = --pos;
          pos++;
          seg.erase(seg.find(*pos - *l));
        }
        if (pos != r) {
          auto r = ++pos;
          pos--;
          seg.erase(seg.find(*r - *pos));
        }
        if (pos != coord.begin() && pos != r) {
          auto l = --pos;
          pos++;
          auto r = ++pos;
          seg.insert(*r - *l);
        }
        coord.erase(coord.find(x));
      }
      int ans;
      if (coord.size() > 2)
        ans = *coord.rbegin() - *coord.begin() - *seg.rbegin();
      else
        ans = 0;
      cout << ans << endl;
    }
  }
  return 0;
}
