#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
struct Node{
    int id;
    int priority;
    struct Node* next;
};

struct Node* createNode(int id,int priority){
    struct Node* newnode=(struct Node*)malloc (sizeof(struct Node));
    newnode->id=id;
    newnode->priority=priority;
    newnode->next=NULL;
    return newnode;
}

void insert(struct Node** head,int id,int priority){
    struct Node* newnode=createNode(id,priority);
    if(*head==NULL || (*head)->priority<priority){
        newnode->next=*head;
        *head=newnode;
    }
    else{
        struct Node* temp=*head;
        while(temp->next != NULL && temp->next->priority>=priority){
            temp=temp->next;
        }
        newnode->next=temp->next;
        temp->next=newnode;
    }
}
void delete(struct Node** head){
    if(*head == NULL){
        printf("Queue is empty\n");
        return ;
    }
    struct Node* temp= *head;
    printf("%d\n",temp->id);
    *head=(*head)->next;
    free(temp);
}
int isNumber(char *str){
    for(int i=0;str[i];i++){
        if(!isdigit(str[i])) return 0;
    }
    return 1;
}
int main(){
    int N;
    if(scanf("%d",&N)!= 1||( N<=0) {
        printf("Invalid input\n");
        return 0;
    }
    struct Node* head=NULL;
    
    for(int i=0;i<N;i++){
        char op[10];
        if(scanf("%s",op)!=1){
            printf("Invalid input\n");
            return 0;
        }
        if(strcmp(op,"INSERT")==0){
            char idStr[20],priorityStr[20];
            if(scanf("%s %s",idStr,priorityStr)!=2 || !isNumber(idStr) || isNumber(priorityStr)){
        printf("Invalid input\n");
        return 0;
        }
        int id=atoi(idStr),priority=atoi(priorityStr);
        insert(&head,id,priority);
        
}else if(strcmp(op,"DELETE")==0){
    delete(&head);
}else{
    printf("Invalid input\n");
    return 0;
}
}
return 0;
}