#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
const int NAX = 1005;
const long long MOD = (long long)(1e9 + 7);
long long N, M, K;
long long X, Y, Z;
long long H, W;
long long B;
long long perform(long long x) { return (x * (x + 1)) / 2LL; }
long long ceilS(long long x, long long y) { return (x + y - 1) / y; }
vector<int> A;
vector<int> adj[MAXN];
using D = long double;
bool inRange(long long a, long long b) { return a * b <= 0; }
int main() {
  long long Q;
  cin >> N >> Q;
  A.resize(N);
  for (auto &x : A) cin >> x;
  set<long long> s;
  multiset<long long> m;
  auto Add = [&](int x) {
    auto ret = s.insert(x);
    auto itr = ret.first;
    if (next(itr) != s.end() && itr != s.begin()) {
      m.erase(m.find(*next(itr) - *prev(itr)));
    }
    if (next(itr) != s.end()) {
      m.insert(*next(itr) - *itr);
    }
    if (itr != s.begin()) {
      m.insert(*itr - *prev(itr));
    }
  };
  auto Remove = [&](int x) {
    auto itr = s.find(x);
    assert(itr != s.end());
    if (next(itr) != s.end() && itr != s.begin()) {
      m.insert(*next(itr) - *prev(itr));
    }
    if (next(itr) != s.end()) {
      m.erase(m.find(*next(itr) - *itr));
    }
    if (itr != s.begin()) {
      m.erase(m.find(*itr - *prev(itr)));
    }
    s.erase(itr);
  };
  for (auto &x : A) Add(x);
  while (Q--) {
    int x;
    cin >> x;
    int pos;
    cin >> pos;
    if (m.empty()) {
      cout << 0 << "\n";
    } else {
      int bottom = *s.begin();
      int top = *s.rbegin();
      cout << top - bottom - *m.rbegin() << "\n";
    }
    if (x) {
      Add(pos);
    } else {
      Remove(pos);
    }
    if (!Q) {
      if (m.empty()) {
        cout << 0 << "\n";
        break;
      }
      int bottom = *s.begin();
      int top = *s.rbegin();
      cout << top - bottom - *m.rbegin() << "\n";
      break;
    }
  }
}
