#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
template <class T>
using vec = std::vector<T>;
bool __hack = std::ios::sync_with_stdio(false);
auto __hack1 = cin.tie(nullptr);
struct Input {
  Input(istream &in) : in(&in) {}
  template <class T>
  T next() const {
    T x;
    *in >> x;
    return x;
  }
  int ni() const { return next<int>(); }
  template <class T>
  vec<T> nVec(int n) const {
    vec<T> v(n);
    for (int i = 0; i < n; ++i) {
      v[i] = next<T>();
    }
    return v;
  }
  vec<int> nvi(int n) const { return nVec<int>(n); }
  istream *in;
};
Input in(cin);
class Output {
 private:
  ostream *out;
  template <typename T>
  void printSingle(const T &value) {
    *out << value;
  }

 public:
  Output(ostream &out) : out(&out) {}
  inline void print() {}
  template <typename T, typename... Ts>
  inline void print(const T &f, const Ts &...args) {
    printSingle(f);
    if (sizeof...(args) != 0) {
      *out << ' ';
      print(args...);
    }
  }
  template <typename... Ts>
  inline void println(const Ts &...args) {
    print(args...);
    *out << '\n';
  }
  template <typename... Ts>
  inline void operator()(const Ts &...args) {
    println(args...);
  }
};
Output out(cout);
namespace template_util {
constexpr int bytecount(uint64_t x) { return x ? 1 + bytecount(x >> 8) : 0; }
template <int N>
struct bytetype {};
template <uint64_t N>
struct minimal_uint : bytetype<bytecount(N)> {};
}  // namespace template_util
void solve(istream &inStream, ostream &outStream) {
  in = Input(inStream);
  out = Output(outStream);
  auto n = in.ni();
  auto q = in.ni();
  auto xs = in.nvi(n);
  sort(xs.begin(), xs.end());
  multiset<int> piles;
  set<int> points(xs.begin(), xs.end());
  for (int i = (1); i < (n); ++i) piles.insert(xs[i] - xs[i - 1]);
  auto get = [&]() -> int {
    if (n <= 2) {
      return 0;
    }
    int mi = *points.begin(), ma = *points.rbegin();
    int mx = *piles.rbegin();
    return ma - mi - mx;
  };
  auto remove = [&](int x) {
    --n;
    auto it = points.find(x);
    int xPrev = -1;
    int xNext = -1;
    if (it != points.begin()) {
      --it;
      xPrev = *it;
      ++it;
      piles.erase(piles.find(x - xPrev));
    }
    ++it;
    if (it != points.end()) {
      xNext = *it;
      --it;
      piles.erase(piles.find(xNext - x));
    }
    points.erase(x);
    if (xPrev != -1 && xNext != -1) {
      piles.insert(xNext - xPrev);
    }
  };
  auto add = [&](int x) {
    ++n;
    points.insert(x);
    auto it = points.find(x);
    int xPrev = -1;
    int xNext = -1;
    if (it != points.begin()) {
      --it;
      xPrev = *it;
      ++it;
      piles.insert(x - xPrev);
    }
    ++it;
    if (it != points.end()) {
      xNext = *it;
      --it;
      piles.insert(xNext - x);
    }
    if (xPrev != -1 && xNext != -1) {
      piles.erase(piles.find(xNext - xPrev));
    }
  };
  out(get());
  while (q--) {
    auto t = in.ni();
    auto x = in.ni();
    if (t == 0) {
      remove(x);
    } else {
      add(x);
    }
    out(get());
  }
}
int main() {
  solve(cin, cout);
  return 0;
}
