#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 200017;
const int p = 37;
void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> p(n + 1);
  multiset<int> q;
  multiset<int> s;
  for (int i = 1; i <= n; i++) cin >> p[i], q.insert(p[i]);
  sort(p.begin() + 1, p.end());
  for (int i = 2; i <= n; i++) s.insert(p[i] - p[i - 1]);
  if (s.size() >= 1)
    cout << *q.rbegin() - *q.begin() - *s.rbegin() << "\n";
  else
    cout << "0\n";
  while (k--) {
    int type, pos;
    cin >> type >> pos;
    if (!type) {
      q.erase(q.find(pos));
      if (q.size() == 0) {
        cout << 0 << "\n";
        continue;
      }
      if (pos > *q.rbegin()) {
        if (s.size() == 0) break;
        s.erase(s.find(pos - *q.rbegin()));
        if (s.size() >= 1)
          cout << *q.rbegin() - *q.begin() - *s.rbegin() << "\n";
        else
          cout << 0 << "\n";
      } else if (pos < *q.begin()) {
        if (s.size() == 0) break;
        s.erase(s.find(*q.begin() - pos));
        if (s.size() >= 1)
          cout << *q.rbegin() - *q.begin() - *s.rbegin() << "\n";
        else
          cout << 0 << "\n";
      } else {
        auto it1 = q.lower_bound(pos);
        auto it2 = q.lower_bound(pos);
        it2--;
        if (s.size() == 0) break;
        s.erase(s.find(*it1 - pos));
        if (s.size() == 0) break;
        s.erase(s.find(pos - *it2));
        s.insert(*it1 - *it2);
        if (s.size() >= 1)
          cout << *q.rbegin() - *q.begin() - *s.rbegin() << "\n";
        else
          cout << 0 << "\n";
      }
    } else {
      if (q.size() == 0) {
        cout << 0 << "\n";
        q.insert(pos);
        continue;
      } else if (pos > *q.rbegin()) {
        s.insert(pos - *q.rbegin());
        q.insert(pos);
        if (s.size() >= 1)
          cout << *q.rbegin() - *q.begin() - *s.rbegin() << "\n";
        else
          cout << 0 << "\n";
      } else if (pos < *q.begin()) {
        s.insert(*q.begin() - pos);
        q.insert(pos);
        if (s.size() >= 1)
          cout << *q.rbegin() - *q.begin() - *s.rbegin() << "\n";
        else
          cout << 0 << "\n";
      } else {
        auto it1 = q.lower_bound(pos);
        auto it2 = it1;
        it2--;
        if (s.size() == 0) break;
        s.erase(s.find(*it1 - *it2));
        s.insert(pos - *it2);
        s.insert(*it1 - pos);
        q.insert(pos);
        if (s.size() >= 1)
          cout << *q.rbegin() - *q.begin() - *s.rbegin() << "\n";
        else
          cout << 0 << "\n";
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t24 = 1;
  while (t24--) {
    solve();
    cout << "\n";
  }
}
