#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <tuple>
#include <set>
#include <string>

using namespace std;

#define int long long

signed main() {
	int n, q;
	cin >> n >> q;
	vector<tuple<int, int>> scores;
	for (int i = 0; i < n; i++) {
		int score;
		cin >> score;
		scores.emplace_back(make_tuple(score, i + 1));
	}
	sort(scores.begin(), scores.end());
	map<int, int> indexes;
	int sameI = n - 1;
	for (int i = n - 1; i >= 0; i--) {
		if (get<0>(scores[i]) != get<0>(scores[sameI]))sameI = i;
		indexes.emplace(get<1>(scores[i]), sameI);
	}

	map<int,int> used_indexes;
	for (int i = 0; i < q; i++) {
		string s;
		int val;
		cin >> s >> val;
		if (s[0] == 'A') {
			used_indexes[indexes[val]]++;
		}
		if (s[0] == 'R') {
			used_indexes[indexes[val]]--;
			if (used_indexes[indexes[val]] <= 0)used_indexes.erase(indexes[val]);
		}
		if (s[0] == 'C') {
			int bottom = -1;
			int top = 2e9;
			while (bottom + 1 < top) {
				int mid = (bottom + top + 1) / 2;//r
				int cnt = 0;
				int prev = -1;
				for (auto index : used_indexes) {
					int bottom2 = -1;
					int top2 = index.first;
					while (bottom2 + 1 < top2) {
						int mid2 = (bottom2 + top2 + 1) / 2;
						if (get<0>(scores[index.first]) 
							- get<0>(scores[mid2]) <= mid) {
							top2 = mid2;
						}
						else {
							bottom2 = mid2;
						}
					}
					if (top2 <= prev)cnt += index.first - prev;
					else cnt += index.first - top2 + 1;
					prev = index.first;
				}

				if (n-cnt<=val)top = mid;
				else bottom = mid;
			}
			if (top == 2e9)cout << "NA" << endl;
			else cout << top << endl;
		}
	}
}
