#include <bits/stdc++.h>
using namespace std;
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
template <class T>
inline bool R(T &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return false;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
  return true;
}
inline bool R(double &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return false;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (ch == '.') {
    double tmp = 1;
    ch = nc();
    for (; ch >= '0' && ch <= '9'; ch = nc())
      tmp /= 10.0, x += tmp * (ch - '0');
  }
  if (sign) x = -x;
  return true;
}
inline bool R(char *s) {
  char ch = nc();
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return false;
  for (; !blank(ch) && !IOerror; ch = nc()) *s++ = ch;
  *s = 0;
  return true;
}
inline bool R(char &c) {
  c = nc();
  if (IOerror) {
    c = -1;
    return false;
  }
  return true;
}
template <class T, class... U>
bool R(T &h, U &...t) {
  return R(h) && R(t...);
}
};  // namespace fastIO
using namespace fastIO;
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.F), putchar(' '), _W(x.S);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head), putchar(sizeof...(tail) ? ' ' : '\n'), W(tail...);
}
const int maxn = 2e5 + 5;
int n, q;
int a[maxn];
set<int> s1;
multiset<int> s2;
inline int solve() {
  if (s1.size() <= 2) return 0;
  return *s1.rbegin() - *s1.begin() - *s2.rbegin();
}
int main() {
  int n, m;
  R(n, m);
  for (int i = 1; i <= n; ++i) R(a[i]), s1.insert(a[i]);
  sort(a + 1, a + 1 + n);
  for (int i = 2; i <= n; ++i) s2.insert(a[i] - a[i - 1]);
  W(solve());
  while (m--) {
    int op, x;
    R(op, x);
    if (op == 1) {
      s1.insert(x);
      if (s1.size() == 1) {
        W(0);
        continue;
      }
      auto it = s1.find(x);
      auto end = s1.end();
      --end;
      if (it == s1.begin()) {
        int x1 = *(++it);
        s2.insert(x1 - x);
      } else if (it == end) {
        int x1 = *(--it);
        s2.insert(x - x1);
      } else {
        int x1 = *(--it);
        ++it;
        int x2 = *(++it);
        s2.erase(s2.find(x2 - x1));
        s2.insert(x2 - x);
        s2.insert(x - x1);
      }
    } else {
      auto it = s1.find(x);
      if (s1.size() == 1) {
        s1.erase(it);
        W(0);
        continue;
      } else if (s1.size() == 2) {
        s1.erase(it);
        s2.erase(s2.begin());
        W(0);
        continue;
      }
      auto end = s1.end();
      --end;
      if (it == s1.begin()) {
        int x1 = *(++it);
        s2.erase(s2.find(x1 - x));
      } else if (it == end) {
        int x1 = *(--it);
        s2.erase(s2.find(x - x1));
      } else {
        int x1 = *(--it);
        ++it;
        int x2 = *(++it);
        s2.erase(s2.find(x2 - x));
        s2.erase(s2.find(x - x1));
        s2.insert(x2 - x1);
      }
      s1.erase(s1.find(x));
    }
    W(solve());
  }
}
