#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
void solve() {
  set<int> pl;
  multiset<int> df;
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; ++i) {
    int first;
    cin >> first;
    pl.insert(first);
  }
  auto it = next(pl.begin());
  ll sum = 0;
  while (it != pl.end()) {
    int diff = *it - *prev(it);
    sum += ll(diff);
    df.insert(diff);
    ++it;
  }
  ll ans = sum;
  if (not df.empty()) ans -= *prev(df.end());
  cout << ans << endl;
  while (q--) {
    int op, first;
    cin >> op >> first;
    if (op == 1) {
      pl.insert(first);
      it = pl.find(first);
      if (it != prev(pl.end())) {
        int diff = *next(it) - *it;
        sum += ll(diff);
        df.insert(diff);
      }
      if (it != pl.begin()) {
        int diff = *it - *prev(it);
        sum += ll(diff);
        df.insert(diff);
      }
      if (it != pl.begin() and it != prev(pl.end())) {
        int diff = *next(it) - *prev(it);
        sum -= ll(diff);
        df.erase(df.find(diff));
      }
    } else {
      it = pl.find(first);
      if (it != prev(pl.end())) {
        int diff = *next(it) - *it;
        sum -= ll(diff);
        df.erase(df.find(diff));
      }
      if (it != pl.begin()) {
        int diff = *it - *prev(it);
        sum -= ll(diff);
        df.erase(df.find(diff));
      }
      if (it != pl.begin() and it != prev(pl.end())) {
        int diff = *next(it) - *prev(it);
        sum += ll(diff);
        df.insert(diff);
      }
      pl.erase(first);
    }
    ans = sum;
    if (not df.empty()) ans -= *prev(df.end());
    cout << ans << endl;
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  solve();
}
