#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
pair<int,int> c[1000000];
int w[1000000];
int at[1000000];
int L[1000000];
char str[10];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		int p;
		scanf("%d",&p);
		c[i]=make_pair(p,i);
	}
	std::sort(c,c+a);
	for(int i=0;i<a;i++)w[i]=c[i].first;
	w[a]=1000000000;
	for(int i=0;i<a;i++)at[c[i].second]=i;
	set<int> S;
	for(int i=0;i<b;i++){
		int v;
		scanf("%s%d",str,&v);
		if(str[0]=='A'){
			L[at[v-1]]=1;
			S.insert(at[v-1]);
		}
		if(str[0]=='R'){
			L[at[v-1]]=0;
			S.erase(at[v-1]);
		}
		if(str[0]=='C'){
			int left=-1;
			int right=1000000007;
			while(left+1<right){
				int M=(left+right)/2;
				int R=-1;
				int C=0;
				for(set<int>::iterator it=S.begin();it!=S.end();it++){
				//	printf("%d\n",*it);
					int l=lower_bound(w,w+a,w[(*it)]-M)-w;
					int r=upper_bound(w,w+a,w[(*it)])-w-1;
					if(R<l){
						C+=l-R-1;
					}
					R=r;
				}
				C+=a-1-R;
				if(C<=v){
					right=M;
				}else left=M;
			}
			if(right==1000000007)printf("NA\n");
			else printf("%d\n",right);
		}
	}
}