#include<bits/stdc++.h>
using namespace std;

multiset<int > s;
bool vis[10001];
int p = 1, k = 1;
int m, n, x;

void del(int p) {
    if(s.empty()) {
        printf("-1\n");
        return ;
    }
    if(p == 1) {
        if(vis[k++]) {
            printf("%d\n", *s.begin());
        }
        s.erase(*s.begin());
    } else if(p == 2) {
        if(vis[k++]) {
            printf("%d\n", *s.rbegin());
        }
        s.erase(*s.rbegin());
    }
}

int main() {
    cin >> m >> n;
    for(int i = 0; i < n; i++) {
        cin >> x;
        vis[x] = true;
    }
    char c;
    while(cin >> c) {
        if(c == 'e') {
            break;
        }
        if(c == 'a') {
            cin >> x;
            s.insert(x);
        } else if(c == 'p') {
            cin >> p;
        } else if(c == 'r') {
            del(p);
        }
    }
    printf("\n");
    // system("pause");
    return 0;
}