#include <iostream>
#include <vector>
#include<algorithm>
#include <math.h>
#include <iomanip>
#include <stack>
#include <string>
#include <set>
#include <map>
using namespace std;
int sz,q;
int tables[(int)1e5+1],freq[(int)1e5+1];
set<int>f_availble[(int)1e5+1];
set<int>dis_sizes;
int main(){
    cin>>sz>>q;
    for (int i=0; i<sz; i++) {
        cin>>tables[i];
        dis_sizes.insert(tables[i]);
        freq[tables[i]]++;
        f_availble[tables[i]].insert(i+1);
    }
    set<int>::iterator myit,t;
    for (int i=0; i<q; i++) {
        string what;
        int n;
        cin>>what>>n;
        if (what=="in") {
            myit = dis_sizes.lower_bound(n);
            if (myit==dis_sizes.end()) {
                cout<<"-1"<<endl;
            }
            else{
                freq[*myit]--;
                if (freq[*myit]==0) {
                    dis_sizes.erase(myit);
                }
                cout<<*(f_availble[*myit].begin())<<endl;
                f_availble[*myit].erase(f_availble[*myit].begin());
            }
        }
        else{
            dis_sizes.insert(tables[n-1]);
            freq[tables[n-1]]++;
            f_availble[tables[n-1]].insert(n);
        }
    }
    return 0;
}