#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i =(a); i <(b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const bool debug = 0;

int N, Q;
int s[1123456];
multiset<int> lp;
int cn;
vector<int> cx;
vector<int> cnt, sum;

int solve(int R) {
	int c = 0;
	
	for (multiset<int>::iterator it = lp.begin(); it != lp.end(); ++it) {
		int idx = lower_bound(ALL(cx), *it) - cx.begin();
		int dnum = *it - R; // [dnum, *it]
		
		multiset<int>::iterator nex = it;
		if (it != lp.begin()) {
			--nex;
			if (*nex == *it) continue;
			chmax(dnum, *nex + 1);
		}
		c += sum[idx + 1] - sum[lower_bound(ALL(cx), dnum) - cx.begin()];
	}
	return N - c;
}

int main() {
	cin >> N >> Q;
	REP(i, N) scanf("%d", s + i);
	
	REP(i, N) cx.push_back(s[i]);
	sort(ALL(cx));
	cx.erase(unique(ALL(cx)), cx.end());
	
	cn = cx.size();
	cnt.resize(cn, 0);
	REP(i, N) cnt[lower_bound(ALL(cx), s[i]) - cx.begin()]++;
	
	sum.resize(cn + 1, 0);
	REP(i, cn) sum[i + 1] = sum[i] + cnt[i];
	
	while (Q--) {
		string qs; int x;
		cin >> qs >> x;
		if (qs == "ADD") {
			lp.insert(s[x - 1]);
		}
		else if (qs == "REMOVE") {
			lp.erase(lp.find(s[x - 1]));
		}
		else {
			// ????????¢?´¢?????????
			int l = -1, r = 1000000001;
			
			while (r - l > 1) {
				int m = (l + r) / 2;
				if (solve(m) <= x) r = m;
				else l = m;
			}
			
			if (r == 1000000001) puts("NA");
			else cout << r << endl;
		}
	}
	
	return 0;
}