// AOJ 0283
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#define rep(i,a) for( int i = 0; i != (a); ++i )

const int MAX_N = 1000000, INF = 1 << 30;

int N, Q;
int s[MAX_N], sorted[MAX_N];

std::multiset<int> ls;

int main()
{
	scanf( "%d%d", &N, &Q );
	rep( i, N )
	{
		scanf( "%d", s+i );
		sorted[i] = s[i];
	}

	std::sort( sorted, sorted+N );

	rep( i, Q )
	{
		char q[7];
		int x;
		scanf( "%s %d", q, &x );
		
		if( *q == 'A' )
			ls.insert( s[x-1] );
		else if( *q == 'R' )
			ls.erase( ls.lower_bound( s[x-1] ) );
		else
		{
			int lb = 0, ub = INF;
			while( ub - lb > 0 )
			{
				int mid = (lb + ub)>>1;
				int prv = 0, loss = 0;

				for( auto it = ls.begin(); it != ls.end(); ++it )
				{
					int p = std::lower_bound( sorted, sorted+N, *it-mid ) - sorted;
					loss += std::max( p-1-prv+1, 0 );
					prv = std::upper_bound( sorted, sorted+N, *it ) - sorted;
				}

				loss += std::max( N-1-prv+1, 0 );

				if( loss <= x )
					ub = mid;
				else
					lb = mid+1;
			}
			if( lb != INF )
				printf( "%d\n", lb );
			else
				puts("NA");
		}
	}

	return 0;
}