#include <cstdio>
#include <map>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

#define INF 1000000010

int main(){
	int n, q;
	char qtype[16] = "";
	int x;
	
	scanf("%d%d", &n, &q);
	vector<int> s0(n);
	for(int i = 0; i < n; ++i){
		scanf("%d", &s0[i]);
	}
	vector<int> s = s0;
	sort(s.begin(), s.end());

	map<int,int> lds;
	map<int,int>::iterator it;
	while(q--){
		scanf("%s%d", qtype, &x);

		if(qtype[0] == 'A'){
			++lds[s0[x - 1]];
		}
		else if(qtype[0] == 'R'){
			it = lds.find(s0[x - 1]);
			if(it == lds.end())throw 0;
			if(!--it->second){
				lds.erase(it);
			}
		}
		else{
			int left = 0, right = INF + 3;
			while(left < right){
				int r = (left + right) >> 1;
				
				int c = n;
				int p = INT_MIN;
				
				for(it = lds.begin(); it != lds.end(); ++it){
					int lim = max(p, it->first - r);
					c -= upper_bound(s.begin(), s.end(), it->first) -
						 lower_bound(s.begin(), s.end(), lim);
					p = it->first + 1;
				}
				
				if(c > x){
					left = r + 1;
				}
				else{
					right = r;
				}
			}
			
			printf(left > INF ? "NA\n" : "%d\n", left);
		}
	}
}