#include <bits/stdc++.h>
using namespace std;
void Fast_IO() {
  ios::sync_with_stdio(0);
  cin.tie(0);
}
int main() {
  Fast_IO();
  long long n, q;
  cin >> n >> q;
  long long a[n];
  for (long long i = (long long)0; i <= (long long)n - 1; i++) cin >> a[i];
  sort(a, a + n);
  long long sum = 0;
  for (long long i = (long long)1; i <= (long long)n - 1; i++)
    sum += a[i] - a[i - 1];
  multiset<long long> ms;
  set<long long> s;
  for (long long i = (long long)0; i <= (long long)n - 1; i++) s.insert(a[i]);
  for (long long i = (long long)1; i <= (long long)n - 1; i++)
    ms.insert(a[i] - a[i - 1]);
  if (!ms.empty()) sum -= *ms.rbegin();
  cout << sum << '\n';
  while (q--) {
    if (!ms.empty()) sum += *ms.rbegin();
    long long ty, x;
    cin >> ty >> x;
    if (ty == 0 && (long long)int(s.size()) == 1) {
      s.clear();
      ms.clear();
      sum = 0;
      cout << 0 << '\n';
      continue;
    } else if (ty == 0 && (long long)int(s.size()) == 2) {
      s.erase(x);
      ms.clear();
      sum = 0;
      cout << 0 << '\n';
      continue;
    } else if (ty == 1 && (long long)int(s.size()) == 0) {
      s.insert(x);
      sum = 0;
      cout << 0 << '\n';
      continue;
    } else if (ty == 1 && (long long)int(s.size()) == 1) {
      s.insert(x);
      sum = 0;
      ms.clear();
      vector<long long> dumb;
      for (auto y : s) dumb.push_back(y);
      sum = abs(dumb[1] - dumb[0]);
      ms.insert(sum);
      cout << 0 << '\n';
      sum = 0;
      continue;
    }
    if (ty == 0) {
      auto it = s.find(x);
      if (it == s.begin()) {
        long long hmm = 0;
        it++;
        hmm += (*it);
        it--;
        hmm -= (*it);
        s.erase(it);
        auto it2 = ms.lower_bound(hmm);
        ms.erase(it2);
        sum -= hmm;
      } else if ((*it) == (*s.rbegin())) {
        long long hmm = 0;
        hmm += (*it);
        it--;
        hmm -= (*it);
        it++;
        s.erase(it);
        auto it2 = ms.lower_bound(hmm);
        ms.erase(it2);
        sum -= hmm;
      } else {
        long long hmm1 = 0, hmm2 = 0;
        it++;
        hmm2 += (*it);
        it--;
        hmm2 -= (*it);
        hmm1 += (*it);
        it--;
        hmm1 -= (*it);
        it++;
        s.erase(it);
        auto it2 = ms.lower_bound(hmm1);
        ms.erase(it2);
        auto it3 = ms.lower_bound(hmm2);
        ms.erase(it3);
        ms.insert(hmm1 + hmm2);
      }
    } else {
      auto it = s.lower_bound(x);
      if (it == s.begin()) {
        long long hmm = (*it) - x;
        s.insert(x);
        sum += hmm;
        ms.insert(hmm);
      } else if (it == s.end()) {
        long long hmm = x - (*s.rbegin());
        s.insert(x);
        sum += hmm;
        ms.insert(hmm);
      } else {
        long long hmm1 = (*it) - x;
        it--;
        long long hmm2 = x - (*it);
        s.insert(x);
        auto it2 = ms.lower_bound(hmm1 + hmm2);
        ms.erase(it2);
        ms.insert(hmm1);
        ms.insert(hmm2);
      }
    }
    if (!ms.empty()) sum -= *ms.rbegin();
    cout << sum << '\n';
  }
  return 0;
}
