#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
typedef map<int,int> mapi;
typedef pair<int,int> pr;
vector<pr> data;
vector<int> leader;
int n,q;
int study(int lo,int hi,int needs){
	if(lo>hi)
	return 0;
	int f=lo,s=hi;
	while(f<=s){
	int mid=(f+s)/2;
	if(data[mid].first>=needs)
		s=mid-1;
	else
		f=mid+1;
	}
	return s-lo+1;
}
bool can(int space,int score){
	int sum=0;
	if(leader[0]!=0)
	sum+=study(0,leader[0]-1,data[leader[0]].first-score);
	for(int i=1;i<leader.size();i++){
	int f=leader[i-1]+1,s=leader[i]-1;
	while(data[f].first==data[f-1].first) f++; 
	sum+=study(f,s,data[leader[i]].first-score);
	}
	int c=0;
	for(int i=leader[leader.size()-1]+1;i<n;i++)
		if(data[i].first==data[i-1].first)
			c++;
		else
			break;
	sum+=n-c-(leader[leader.size()-1]+1);
	return space>=sum;

}
int search(int space){
	int f=0,s=pow(10,9);
	while(f<=s){
	int mid=(f+s)/2;
	if(can(space,mid))
		s=mid-1;
	else
		f=mid+1;
	}
	return f;
}
int main() {
	// your code goes here
	int tmp;
	string tmps;
	while(cin >>n >> q && n!=0){
	mapi point;
		for(int i=0;i<n;i++){
			cin >> tmp;
			//point.insert(mapi::value_type(i+1,tmp));
			data.push_back(pr(tmp,i+1));
		}
		sort(data.begin(),data.end());
		for(int i=0;i<n;i++)
			point.insert(mapi::value_type(data[i].second,i));

		for(int j=0;j<q;j++){
			cin >> tmps >> tmp;
			if(tmps=="ADD")
				leader.push_back(point[tmp]);
			if(tmps=="REMOVE"){
				for(vector<int>::iterator it=leader.begin()++;it!=leader.end();++it)
					if(*it==point[tmp]){
						it=leader.erase(it);
						break;
					}
			}
			if(tmps=="CHECK"){
				int ans;
				if(leader.size()==0){
					if(tmp<n)
						ans=1000000001;
					else
						ans=0;
				}
				else
				ans=search(tmp);
				if(ans==1000000001)
				cout << "NA" << endl;
				else
				cout << ans << endl;
			}
			else
			sort(leader.begin(),leader.end());
		}
		
		data.clear();
		leader.clear();
	}
	return 0;
}