#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long int n, q;
  cin >> n >> q;
  vector<long long int> p(n);
  set<long long int> piles;
  for (long long int i = 0; i < n; i++) {
    cin >> p[i];
    piles.insert(p[i]);
  }
  sort(p.begin(), p.end());
  multiset<long long int> segments;
  for (long long int i = 1; i < n; i++) {
    segments.insert(p[i] - p[i - 1]);
  }
  long long int dist = p[n - 1] - p[0];
  if (!segments.empty()) {
    auto it = --segments.end();
    dist -= *it;
  }
  cout << dist << '\n';
  while (q--) {
    long long int type, pos;
    cin >> type >> pos;
    if (type == 0) {
      auto it = piles.find(pos);
      long long int added = 0;
      if (it != piles.begin()) {
        it--;
        long long int segment = pos - *it;
        segments.erase(segments.find(segment));
        it++;
        added += segment;
      }
      it++;
      if (it != piles.end()) {
        long long int segment = *it - pos;
        segments.erase(segments.find(segment));
        added += segment;
      }
      it--;
      if (it != piles.begin() && (++it) != piles.end()) {
        segments.insert(added);
      }
      piles.erase(piles.find(pos));
    } else {
      if (!piles.empty()) {
        auto it = piles.lower_bound(pos);
        if (it != piles.end()) {
          long long int next = *it;
          long long int segment = next - pos;
          segments.insert(segment);
        }
        if (it != piles.begin()) {
          it--;
          long long int prev = *it;
          long long int segment = pos - prev;
          segments.insert(segment);
          it++;
        }
        if (it != piles.begin() && it != piles.end()) {
          long long int next = *it;
          long long int prev = *(--it);
          long long int segment = next - prev;
          segments.erase(segments.find(segment));
        }
      }
      piles.insert(pos);
    }
    long long int dist = 0;
    if (!piles.empty()) {
      dist = (*(--piles.end())) - (*piles.begin());
      if (!segments.empty()) {
        dist -= *(--segments.end());
      }
    }
    cout << dist << '\n';
  }
  return 0;
}
