Language: C++

#include <iostream>
#include <vector>
#include <set>
#include <iterator>

using namespace std;

typedef long long LL;

template <class T>
struct BIT/*{{{*/
{
  vector<T> tree;
  const int size;
  BIT(int s) : tree(s), size(s) {}
  // i 番目までの要素の累積和
  T read(int i) const
  {
    T sum = 0;
    while (i > 0) {
      sum += tree[i];
      i -= i & -i;
    }
    return sum;
  }

  // i 番目の要素
  T read_single(int i) const
  {
    T sum = tree[i];
    if (i > 0) {
      const int z = i - (i & -i);
      --i;
      while (i != z) {
        sum -= tree[i];
        i -= (i & -i);
      }
    }
    return sum;
  }

  void add(int i, T v)
  {
    while (i <= size) {
      tree[i] += v;
      i += (i & -i);
    }
  }

  // read(i) == vとなる最小のi。存在しなければ-1。
  int search(T v) {
        int left = 0, right = size;
        while(left+1 < right) {
            const int center = (left+right) / 2;
            if(read(center) < v) {
                left = center;
            } else {
                right = center;
            }
        }
        if(right == size || read(right) != v) return -1;
        return right;
    }
};/*}}}*/

bool solve() {
    int N, Q;
    if(!(cin >> N >> Q)) return false;
    if(!N && !Q) return false;

    BIT<LL> bit(N+10);
    vector<LL> scores(N);
    LL LIM = 0;
    for(int i = 0; i < N; ++i) {
        cin >> scores[i];
        LIM += scores[i];
    }
    vector<LL> score_list = scores;
    score_list.push_back(-1); // sentinel
    sort(begin(score_list), end(score_list));
    score_list.erase(unique(begin(score_list), end(score_list)), end(score_list));
    for(int i = 0; i < N; ++i) {
        scores[i] = lower_bound(begin(score_list), end(score_list), scores[i]) - begin(score_list);
        bit.add(scores[i], 1);
    }

    multiset<int> leaders;
    for(int _ = 0; _ < Q; ++_) {
        string query;
        int x;
        cin >> query >> x;
        if(query == "ADD") {
            leaders.insert(x-1);
            bit.add(scores[x-1], -1);
        } else if(query == "REMOVE") {
            leaders.erase(leaders.find(x-1));
            bit.add(scores[x-1], 1);
        } else if(query == "CHECK") {
            if(leaders.size() == 0) {
                if(x >= N) cout << 0 << endl;
                else cout << "NA" << endl;
            } else {
                bool found = false;
                LL left = -1, right = LIM;
                while(left+1 < right) {
                    const LL r = (left + right) / 2;
                    LL outlier = 0;
                    LL prev_score = -1;
                    LL prev_leader = -1;
                    for(auto leader : leaders) {
                        const LL score = score_list[scores[leader]];
                        if(score - r - 1 > prev_score) {
                            int lim = lower_bound(begin(score_list), end(score_list), score - r - 1) - begin(score_list);
                            if(score_list[lim] > score - r - 1) --lim;
                            outlier += bit.read(lim) - (prev_leader == -1 ? 0 : bit.read(scores[prev_leader]));
                        }
                        prev_score = score;
                        prev_leader = leader;
                    }
                    outlier += bit.read(N+5) - bit.read(scores[prev_leader]);
                    if(outlier <= x) {
                        right = r;
                        found = true;
                    } else {
                        left = r;
                    }
                }
                if(found) cout << right << endl;
                else cout << "NA" << endl;
            }
        }
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    while(solve()) ;
    return 0;
}

Compiler output:
a.cc: In function 'bool solve()':
a.cc:80:5: error: 'sort' was not declared in this scope; did you mean 'short'?
   80 |     sort(begin(score_list), end(score_list));
      |     ^~~~
      |     short
a.cc:81:22: error: 'unique' was not declared in this scope
   81 |     score_list.erase(unique(begin(score_list), end(score_list)), end(score_list));
      |                      ^~~~~~