#include <bits/stdc++.h>
std::mt19937_64 rng(
    std::chrono::steady_clock::now().time_since_epoch().count());
long long int myRand(long long int R) {
  long long int val = rng() % R;
  assert(val >= 0);
  return val;
}
const long double PI = atan(1.0) * 4;
const int64_t INF64 = 3e18;
const int32_t INF32 = 2e9 + 7;
const int32_t LOG = 21;
const int32_t MOD = 1e9 + 7;
using namespace std;
void my_debugger(string second, long long int LINE_NUM) { cerr << '\n'; }
template <typename start, typename... end>
void my_debugger(string second, long long int LINE_NUM, start x, end... y) {
  if (second.back() != ',') {
    second += ',';
    cerr << "LINE(" << LINE_NUM << "): ";
  }
  long long int i = second.find(',');
  cerr << second.substr(0, i) << " = " << x;
  second = second.substr(i + 1);
  if (!second.empty()) cerr << ", ";
  my_debugger(second, LINE_NUM, y...);
}
long long int find1(long long int sum,
                    set<pair<long long int, long long int>,
                        greater<pair<long long int, long long int>>>& second) {
  if (second.empty()) return 0;
  long long int ans = sum - (second.begin()->first);
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  long long int tests = 1;
  for (long long int ii = 0; ii < (long long int)tests; ii++) {
    set<long long int> second;
    set<long long int, greater<long long int>> s1;
    set<pair<long long int, long long int>,
        greater<pair<long long int, long long int>>>
        dist;
    second.insert(-1);
    second.insert(INF32);
    s1.insert(-1);
    s1.insert(INF32);
    long long int sum = 0;
    long long int n, q;
    cin >> n >> q;
    long long int a[n];
    for (long long int i = 0; i < (long long int)n; i++) {
      cin >> a[i];
      second.insert(a[i]);
      s1.insert(a[i]);
    }
    sort(a, a + n);
    for (long long int i = 1; i < (long long int)n; i++) {
      sum += (a[i] - a[i - 1]);
      dist.insert({a[i] - a[i - 1], a[i - 1]});
    }
    cout << find1(sum, dist) << '\n';
    for (long long int i = 1; i < (long long int)q + 1; i++) {
      long long int x, y;
      cin >> x >> y;
      if (x == 0) {
        second.erase(y);
        s1.erase(y);
        long long int it1 = *second.lower_bound(y);
        long long int it2 = *s1.lower_bound(y);
        if (it1 != INF32) {
          dist.erase({it1 - y, y});
          sum -= (it1 - y);
        }
        if (it2 != -1) {
          dist.erase({y - it2, it2});
          sum -= (y - it2);
        }
        if (it2 != -1 && it1 != INF32) {
          dist.insert({it1 - it2, it2});
          sum += (it1 - it2);
        }
        cout << find1(sum, dist) << '\n';
      } else {
        long long int it1 = *second.lower_bound(y);
        long long int it2 = *s1.lower_bound(y);
        if (it2 != -1 && it1 != INF32) {
          dist.erase({it1 - it2, it2});
          sum -= (it1 - it2);
        }
        if (it1 != INF32) {
          dist.insert({it1 - y, y});
          sum += (it1 - y);
        }
        if (it2 != -1) {
          dist.insert({y - it2, it2});
          sum += (y - it2);
        }
        second.insert(y);
        s1.insert(y);
        cout << find1(sum, dist) << '\n';
      }
    }
  }
  return 0;
}
