#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <tuple>
#include <iostream>
#include <deque>
#include <array>
#include <set>
#include <functional>
#include <memory>
#include <stack>
#include <numeric>
#include <climits>
#include <cfloat>

template<typename F>
int upper_bound(int from, int until, const F& vec, const int target) {
	while (from < until) {
		const auto mid = (from + until) / 2;
		if (vec(mid) <= target) from = mid + 1;
		else until = mid;
	}
	return from;
}
template<typename F>
int lower_bound(int from, int until, const F &vec, const int target) {
	while (from < until) {
		const auto mid = (from + until) / 2;
		if (vec(mid) < target) from = mid + 1;
		else until = mid;
	}
	return from;
}
class Bit {
	std::vector<int> array;
public:
	Bit(const int size) : array(size, 0) {}
	int count(const int from, const int until) const {
		return count_to(until - 1) - count_to(from - 1);
	}
	int count_to(const int to) const {
		return (to >= 0) ? array[to] + count_to(to - (~to & (to + 1))) : 0;
	}
	void increment(const int position) {
		if (position < array.size()) {
			++array[position];
			increment(position + (~position & (position + 1)));
		}
	}
	void decrement(const int position) {
		if (position < array.size()) {
			--array[position];
			decrement(position + (~position & (position + 1)));
		}
	}
};
int main() {
	constexpr int max_leader_count = 100;
	int n, q; std::cin >> n >> q;
	std::vector<int> scores(n); for (auto& s : scores) std::cin >> s;
	std::vector<int> sorted(n); for (auto i = 0; i < n; ++i) sorted[i] = i; std::sort(sorted.begin(), sorted.end(), [&scores](const int a, const int b) {return scores[a] < scores[b]; });
	std::vector<int> index_to_rank(n); for (auto i = 0; i < n; ++i) index_to_rank[sorted[i]] = i;
	std::set<int> leader_set;
	Bit non_leader(n); for (auto i = 0; i < n; ++i) non_leader.increment(i);
	std::vector<int> leader; leader.reserve(max_leader_count);
	auto converter = [&scores, &sorted](const int pos) {return scores[sorted[pos]]; };
	for (auto _i = 0; _i < q; ++_i) {
		std::string op; int a; std::cin >> op >> a;
		if (op == "ADD") {
			leader_set.insert(index_to_rank[a - 1]);
			non_leader.decrement(index_to_rank[a - 1]);
		}
		else if (op == "REMOVE") {
			leader_set.erase(index_to_rank[a - 1]);
			non_leader.increment(index_to_rank[a - 1]);
		}
		else if (op == "CHECK") {
			if (n - leader_set.size() <= a) {
				std::cout << "0\n";
			}
			else if (leader_set.empty()) {
				std::cout << "NA\n";
			}
			else {
				leader.clear(); std::transform(leader_set.begin(), leader_set.end(), std::back_inserter(leader), converter);
				std::sort(leader.begin(), leader.end());
				int min = 0;
				int max = scores[sorted.back()] + 1;
				while (min < max) {
					auto mid = (min + max) / 2;
					auto count = non_leader.count(lower_bound(0, n, converter, leader.front() - mid), upper_bound(0, n, converter, leader.front()));
					for (auto i = 1; i < leader.size(); ++i) {
						if (leader[i] - mid > leader[i - 1]) {
							count += non_leader.count(lower_bound(0, n, converter, leader[i] - mid), upper_bound(0, n, converter, leader[i]));
						}
						else {
							count += non_leader.count(upper_bound(0, n, converter, leader[i - 1]), upper_bound(0, n, converter, leader[i]));
						}
					}
					if (n - leader.size() - count > a) min = mid + 1;
					else max = mid;
				}
				if (max == scores[sorted.back()] + 1) std::cout << "NA\n";
				else std::cout << max << "\n";
			}
		}
	}
}


Measured memory_bytes: 18444