#include <bits/stdc++.h>
using namespace std;
long long int div_floor(const long long int &a, const long long int &b) {
  return a / b - (((a ^ b) < 0) and a % b);
}
long long int div_ceil(const long long int &a, const long long int &b) {
  return a / b + (((a ^ b) >= 0) and a % b);
}
int minimum(multiset<long long int> &a) {
  if (a.empty())
    return 0;
  else
    return *a.rbegin();
}
void solve() {
  long long int n, q;
  cin >> n >> q;
  multiset<long long int> a;
  for (int i = 0; i < n; i++) {
    long long int t;
    cin >> t;
    a.insert(t);
  }
  long long int sum = 0;
  multiset<long long int> dif;
  auto it = a.begin();
  while (it != a.end()) {
    long long int curr = -*it;
    it++;
    if (it == a.end()) break;
    curr += *it;
    dif.insert(curr);
    sum += curr;
  }
  cout << sum - minimum(dif) << '\n';
  for (int i = 0; i < q; i++) {
    int t, e;
    cin >> t >> e;
    if (t == 1) {
      if (a.empty())
        a.insert(e);
      else if (a.upper_bound(e) == a.end())
        dif.insert(e - *a.rbegin()), sum += e - *a.rbegin(), a.insert(e);
      else if (a.upper_bound(e) == a.begin())
        dif.insert(*a.begin() - e), sum += *a.begin() - e, a.insert(e);
      else {
        auto it1 = a.upper_bound(e);
        auto it2 = it1;
        it2--;
        dif.erase(dif.lower_bound(*it1 - *it2));
        dif.insert(e - *it2);
        dif.insert(*it1 - e);
        a.insert(e);
      }
    } else {
      auto it = a.find(e);
      auto it1 = it;
      it1++;
      auto it2 = it;
      if (it != a.begin()) it2--;
      if (a.size() == 1)
        a.erase(it);
      else if (it == a.begin())
        dif.erase(dif.find(*it1 - *it)), sum -= *it1 - *it, a.erase(it);
      else if (it1 == a.end())
        dif.erase(dif.find(*it - *it2)), sum -= *it - *it2, a.erase(it);
      else
        dif.erase(dif.find(*it1 - *it)), dif.erase(dif.find(*it - *it2)),
            dif.insert(*it1 - *it2), a.erase(it);
    }
    cout << sum - minimum(dif) << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t = 1;
  while (t--) solve();
}
