#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9 + 7;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int T = clock();
  long long int n, q;
  cin >> n >> q;
  set<long long int> s;
  multiset<long long int> pq;
  vector<long long int> tmp(n);
  for (long long int i = 0; i < n; i++) {
    cin >> tmp[i];
    s.insert(tmp[i]);
  }
  sort(tmp.begin(), tmp.end());
  unordered_map<long long int, long long int> prev, next;
  prev[tmp[0]] = -1;
  next[tmp[n - 1]] = -1;
  for (long long int i = 1; i < n; i++) prev[tmp[i]] = tmp[i - 1];
  for (long long int i = 0; i < n - 1; i++) next[tmp[i]] = tmp[i + 1];
  long long int tot = 0;
  for (long long int i = 1; i < n; i++) pq.insert(tmp[i] - tmp[i - 1]);
  tot = *s.rbegin() - *s.begin();
  if (pq.size() == 0)
    cout << 0 << "\n";
  else
    cout << tot - *pq.rbegin() << "\n";
  while (q--) {
    long long int c, p;
    cin >> c >> p;
    if (c == 1) {
      if (s.size() == 0) {
        s.insert(p);
        cout << 0 << "\n";
        continue;
      }
      auto it = s.lower_bound(p);
      if (it == s.end()) {
        long long int d = (p - *s.rbegin());
        pq.insert(d);
      } else if (it == s.begin()) {
        long long int d = *s.begin() - p;
        pq.insert(d);
      } else {
        long long int g = *it;
        --it;
        long long int l = *it;
        pq.erase(pq.lower_bound(g - l));
        pq.insert(p - l);
        pq.insert(g - p);
      }
      s.insert(p);
    } else {
      auto uit = s.upper_bound(p);
      auto lit = s.lower_bound(p);
      if (s.size() == 1)
        ;
      else if (uit == s.end()) {
        lit--;
        long long int d = p - *lit;
        pq.erase(pq.lower_bound(d));
      } else if (lit == s.begin()) {
        long long int d = *uit - p;
        pq.erase(pq.lower_bound(d));
      } else {
        long long int g = *uit, l = *(--lit);
        pq.erase(pq.lower_bound(p - l));
        pq.erase(pq.lower_bound(g - p));
        pq.insert(g - l);
      }
      s.erase(p);
    }
    if (s.size() == 0 || pq.size() == 0) {
      cout << 0 << "\n";
      continue;
    }
    tot = *s.rbegin() - *s.begin();
    cout << tot - *pq.rbegin() << "\n";
  }
  cerr << "\n\nTIME: " << (double)(clock() - T) / CLOCKS_PER_SEC << " sec\n";
  T = clock();
  return 0;
}
