#include <bits/stdc++.h>
using namespace std;
template <typename T>
void cetak(T t) {
  cout << t << ')' << endl;
}
template <typename T, typename... V>
void cetak(T t, V... v) {
  cout << t;
  if (sizeof...(v)) cout << ", ";
  cetak(v...);
}
typedef int (*func)(int, int);
const int mx = 1e5 + 10;
set<int> isi;
map<int, int> cnt;
priority_queue<int> pq;
void add(int x) {
  isi.insert(x);
  auto it = isi.lower_bound(x);
  if (next(it) != isi.end()) {
    cnt[*next(it) - *it] += 1;
    pq.push(*next(it) - *it);
  }
  if (it != isi.begin()) {
    cnt[*it - *prev(it)] += 1;
    pq.push(*it - *prev(it));
  }
  if (next(it) != isi.end() && it != isi.begin()) {
    cnt[*next(it) - *prev(it)] -= 1;
  }
}
void rem(int x) {
  auto it = isi.lower_bound(x);
  if (next(it) != isi.end()) {
    cnt[*next(it) - *it] -= 1;
  }
  if (it != isi.begin()) {
    cnt[*it - *prev(it)] -= 1;
  }
  if (next(it) != isi.end() && it != isi.begin()) {
    cnt[*next(it) - *prev(it)] += 1;
    pq.push(*next(it) - *prev(it));
  }
  isi.erase(x);
}
void ans() {
  if ((int)(isi.size()) <= 2)
    cout << 0 << '\n';
  else {
    int tot = *prev(isi.end()) - *isi.begin();
    while (cnt[pq.top()] == 0) pq.pop();
    cout << tot - pq.top() << '\n';
  }
}
void solve(int tc) {
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    add(x);
  }
  ans();
  while (q--) {
    int t;
    cin >> t;
    int x;
    cin >> x;
    if (t == 0)
      rem(x);
    else
      add(x);
    ans();
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  int tc = 0;
  while (t--) {
    solve(++tc);
  }
}
