#include <bits/stdc++.h>
using namespace std;
int p[1000000];
multiset<int> difs;
set<int> s;
void testCase() {}
int totalCost() {
  if (s.size() < 2) return 0;
  auto it = s.begin();
  int pieni = *it;
  it = s.end();
  it--;
  int iso = *it;
  return iso - pieni;
}
int maxDist() {
  if (difs.size() == 0) return 0;
  auto it = difs.end();
  it--;
  return (*it);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) cin >> p[i];
  for (int i = 0; i < n; i++) s.insert(p[i]);
  sort(p, p + n);
  for (int i = 0; i < n - 1; i++) {
    difs.insert(p[i + 1] - p[i]);
  }
  cout << totalCost() - maxDist() << "\n";
  for (int i = 0; i < q; i++) {
    int t, x;
    cin >> t >> x;
    if (t == 0) {
      if (s.size() == 1) {
        s.erase(x);
        cout << totalCost() - maxDist() << "\n";
        continue;
      }
      int suurempi = 0, pienempi = 0;
      auto it = s.upper_bound(x);
      if (it == s.end()) {
        suurempi = -1;
      } else {
        suurempi = *it;
      }
      it = s.lower_bound(x);
      if (it == s.begin()) {
        pienempi = -1;
      } else {
        it--;
        pienempi = *it;
      }
      if (pienempi != -1 && suurempi != -1) {
        difs.erase(difs.find(x - pienempi));
        difs.erase(difs.find(suurempi - x));
        difs.insert(suurempi - pienempi);
      } else if (pienempi != -1) {
        difs.erase(difs.find(x - pienempi));
      } else if (suurempi != -1) {
        difs.erase(difs.find(suurempi - x));
      }
      s.erase(x);
    } else {
      if (s.size() == 0) {
        s.insert(x);
        cout << totalCost() - maxDist() << "\n";
        continue;
      }
      auto it = s.upper_bound(x);
      int suurempi = 0, pienempi = 0;
      if (it == s.end()) {
        suurempi = -1;
      } else {
        suurempi = *it;
      }
      it = s.lower_bound(x);
      if (it == s.begin()) {
        pienempi = -1;
      } else {
        it--;
        pienempi = *it;
      }
      if (pienempi != -1 && suurempi != -1) {
        it = difs.find(suurempi - pienempi);
        difs.erase(it);
        difs.insert(x - pienempi);
        difs.insert(suurempi - x);
      } else if (pienempi != -1) {
        difs.insert(x - pienempi);
      } else if (suurempi != -1) {
        difs.insert(suurempi - x);
      }
      s.insert(x);
    }
    cout << totalCost() - maxDist() << "\n";
  }
}
