#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

int N, Q;
int s[1000000], ss[1000000];
std::vector<int> leaders;

int main(){
    std::cin >> N >> Q;

    REP(i, N){
        std::cin >> s[i];
        ss[i] = s[i];
    }

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

    REP(i, Q){
        std::string query;
        std::cin >> query;

        if(query == "ADD"){
            int a;
            std::cin >> a;
            a -= 1;

            leaders.push_back(a);
        }else if(query == "REMOVE"){
            int a;
            std::cin >> a;
            a -= 1;

            leaders.erase(std::find(leaders.begin(), leaders.end(), a));
        }else{
            int x;
            std::cin >> x;

            int lb = -1, ub = INF;
            while(ub - lb > 1){
                int mid = (lb+ub) / 2;
                std::vector<P> bs;
                
                for(auto l : leaders){
                    bs.push_back(mp(s[l]-mid, s[l]));
                }

                std::sort(bs.begin(), bs.end(),
                          [](const P& lhs, const P& rhs){if(lhs.first != rhs.first){return lhs.first < rhs.first;} return lhs.second < rhs.second;});

                for(int i=0;i+1<(int)bs.size();){
                    if(bs[i].first <= bs[i+1].first && bs[i+1].first <= bs[i].second){
                        bs[i].second = bs[i+1].second;
                        bs.erase(bs.begin()+i+1);
                    }else{
                        i += 1;
                    }
                }

                int res = 0;
                for(auto b : bs){
                    res += std::upper_bound(ss, ss+N, b.second) - std::lower_bound(ss, ss+N, b.first);
                }

                if(N-res <= x){
                    ub = mid;
                }else{
                    lb = mid;
                }
            }

            if(ub != INF){
                std::cout << ub << std::endl;
            }else{
                std::cout << "NA" << std::endl;
            }
        }
    }
}