#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 1;
int main() {
  int N, Q;
  cin >> N >> Q;
  set<int> all;
  multiset<int> gaps;
  for (int i = 0; i < N; ++i) {
    int x;
    cin >> x;
    all.insert(x);
  }
  for (auto iter = all.begin(); iter != all.end(); ++iter) {
    auto nxt = next(iter);
    if (nxt != all.end()) {
      gaps.insert(*nxt - *iter);
    }
  }
  cout << ((all.size() > 2)
               ? ((*prev(all.end()) - *all.begin()) - *prev(gaps.end()))
               : 0)
       << endl;
  while (Q--) {
    int type;
    int x;
    cin >> type >> x;
    if (type) {
      auto iter = all.insert(x).first;
      if (all.size() > 1) {
        if (iter == all.begin()) {
          gaps.insert(*next(iter) - *iter);
        } else if (iter == prev(all.end())) {
          gaps.insert(*iter - *prev(iter));
        } else {
          int gap_l = *next(iter) - *iter;
          int gap_r = *iter - *prev(iter);
          auto gap_old = gaps.find(*next(iter) - *prev(iter));
          gaps.erase(gap_old);
          gaps.insert(gap_l);
          gaps.insert(gap_r);
        }
      }
    } else {
      auto cur = all.find(x);
      if (cur == all.begin() && all.size() > 1) {
        gaps.erase(gaps.find(*next(cur) - *cur));
      } else if (cur == prev(all.end()) && all.size() > 1) {
        gaps.erase(gaps.find(*cur - *prev(cur)));
      } else if (all.size() > 2) {
        auto prv = prev(cur);
        auto nxt = next(cur);
        auto gap1_old = gaps.find(*cur - *prv);
        gaps.erase(gap1_old);
        auto gap2_old = gaps.find(*nxt - *cur);
        gaps.erase(gap2_old);
        gaps.insert(*nxt - *prv);
      }
      all.erase(x);
    }
    cout << ((all.size() > 2)
                 ? ((*prev(all.end()) - *all.begin()) - *prev(gaps.end()))
                 : 0)
         << endl;
  }
}
