#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
constexpr int INF = 0x7f7f7f7f;
constexpr double EPS = 1e-8;
long long fastPow(long long num, long long exp, long long modNum) {
  if (exp == 0) return 1;
  if (exp == 1)
    return num;
  else {
    long long half = fastPow(num, exp / 2, modNum) % modNum;
    if (exp % 2 == 1) {
      return (((half * half) % modNum) * num) % modNum;
    } else {
      return (half * half) % modNum;
    }
  }
}
long long fastPow(long long num, long long exp) {
  if (exp == 0) return 1;
  if (exp == 1)
    return num;
  else {
    long long half = fastPow(num, exp / 2);
    if (exp % 2 == 1) {
      return (((half * half)) * num);
    } else {
      return (half * half);
    }
  }
}
long long getReverse(long long y, long long modNum) {
  return fastPow(y, modNum - 2, modNum) % modNum;
}
long long gcd(long long a, long long b) {
  if (a < b) swap(a, b);
  return (a % b == 0) ? b : gcd(b, a % b);
}
long long find(long long k, vector<long long>& F) {
  return F[k] == k ? k : F[k] = find(F[k], F);
}
template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
void insert(long long num, set<long long>& room, priority_queue<long long>& pq,
            unordered_map<long long, long long>& exempt) {
  if (room.empty()) {
    room.emplace(num);
    return;
  }
  auto lower = room.lower_bound(num);
  if (lower == room.end()) {
    pq.emplace(num - *(--lower));
    room.emplace(num);
    return;
  }
  if (lower == room.begin()) {
    pq.emplace(*lower - num);
    room.emplace(num);
    return;
  }
  auto before = prev(lower);
  pq.emplace(*lower - num);
  pq.emplace(num - *before);
  exempt[*lower - *before]++;
  room.emplace(num);
}
void remove(long long num, set<long long>& room, priority_queue<long long>& pq,
            unordered_map<long long, long long>& exempt) {
  auto lower = room.lower_bound(num);
  if (lower == --room.end()) {
    exempt[num - *(--lower)]++;
    room.erase(num);
    return;
  }
  if (lower == room.begin()) {
    exempt[*(++lower) - num]++;
    room.erase(num);
    return;
  }
  auto before = prev(lower);
  exempt[*(++lower) - num]++;
  exempt[num - *before]++;
  pq.emplace(*lower - *before);
  room.erase(num);
}
long long myTop(priority_queue<long long>& pq,
                unordered_map<long long, long long>& exempt) {
  while (exempt[pq.top()]) {
    exempt[pq.top()]--;
    pq.pop();
  }
  if (pq.empty()) return 0;
  return pq.top();
}
void query(priority_queue<long long>& pq, set<long long>& room,
           unordered_map<long long, long long>& exempt) {
  long long output = 0;
  ;
  if (room.size() <= 2) {
    ;
    cout << output << endl;
    return;
  }
  output = *(--room.end()) - *(room.begin()) - myTop(pq, exempt);
  ;
  cout << output << endl;
}
int main(int argn, char** argv) {
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);
  const long long MOD = 1e9 + 7;
  int T = 1;
  for (int(I) = (0); (I) <= ((T)-1); (I)++) {
    long long n, q;
    cin >> n >> q;
    set<long long> room;
    priority_queue<long long> pq;
    unordered_map<long long, long long> exempt;
    for (int(i) = (0); (i) <= ((n)-1); (i)++) {
      long long temp;
      cin >> temp;
      insert(temp, room, pq, exempt);
    }
    query(pq, room, exempt);
    for (int(i) = (0); (i) <= ((q)-1); (i)++) {
      long long type, num;
      cin >> type >> num;
      if (type) {
        insert(num, room, pq, exempt);
      } else {
        remove(num, room, pq, exempt);
      }
      query(pq, room, exempt);
    }
  }
  return 0;
}
