#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define ALL(v) (v).begin(), (v).end()
#define REV(s) (s).rbegin(), (s).rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int N = 1000010;

int s[N];
int ss[N];

int n, q;
inline int u_b(int x){
	return upper_bound(ss, ss+n, x)-ss;
}

inline int l_b(int x){
	return lower_bound(ss, ss+n, x)-ss;
}

const int INF = (1<<30)-10;

vector<P> leader;
void check(int x){
	sort(ALL(leader));
	int lb = -1, ub = INF;
	while(ub-lb > 1){
		int r = (lb+ub)/2;
		int cnt = 0;
		int prev = 0;
		rep(i, leader.size()){
			int b = u_b(leader[i].first)-1;
			int a = l_b(max(ss[prev], leader[i].first-r));
			cnt += b-a+1;
			prev = u_b(leader[i].first);
		}
		if(n-cnt <= x) ub = r;
		else lb = r;
	}
	if(ub != INF) cout << ub << endl;
	else cout << "NA" << endl;
}

int main(){
	ios::sync_with_stdio(false);

	cin >> n >> q;
	rep(i, n) cin >> s[i], ss[i] = s[i];
	sort(ss, ss+n);
	ss[n] = INF;

	while(q--){
		int a;
		string t;
		cin >> t >> a;
		switch(t[0]){
		case 'A':
			leader.push_back(MP(s[a-1], a-1));
			break;
		case 'R':
			leader.erase(remove(ALL(leader), MP(s[a-1], a-1)));
			break;
		case 'C':
			check(a);
			break;
		}
	}

	return 0;
}