#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 1000
 struct task{
     int id;
     int p;
 };
  struct task heap[MAX];
 int size = 0;
 void swap(struct task*a,struct task*b){
     struct task temp = *a;
     *a = *b;
     *b = temp;
 }
 void heapify_up(int index){
     if(index<=0)
    return;
     int parent=(index-1)/2;
         if(heap[index].p<heap[parent].p){
         swap (&heap[index],&heap[parent]);
         heapify_up(parent);
     }
 }
 void heapify_down(int index) {
     int left=2*index+1;
     int right=2*index+2;
     int smallest=index;
     if(left<size&&heap[left].p<heap[smallest].p)
 smallest=left;
 if(right<size&&heap[right].p<heap[smallest].p)
 smallest=right;
 if(smallest !=index)
 {
    swap(&heap[index],&heap[smallest]);
    heapify_down(smallest);
 }
 }
 void insert(int id,int p){
     heap[size].id=id;
     heap[size].p=p;
     heapify_up(size);
     size++;
     printf("Task Added: %d\n",id);
 }
  struct task extract_task(){
  struct task min_task = heap[0];
  heap[0]= heap[size-1];
  size--;
  heapify_down(0);
  return min_task;
  }
  int main(){
      char command[20];
       int value;
       
       while (scanf("%s", command) != EOF) {
           if (strcmp(command, "add") == 0) {
               if (scanf("%d", &value) != 1 || value < 1|| value > 1000){
                   printf("Invalid input\n");
                    continue;
               }
               insert(value, value);
           } else if(strcmp(command, "remove") == 0) {
               char extra[10];
               if(scanf("%s", extra) == 1) {
                   printf("Invalid input\n");
                   continue;
               }
               if (size == 0) {
                   printf("Invalid input\n");
               } else {
                   struct task t = extract_task();
                   printf("Task Removed: %d\n", t.id);
               }
           } else {
               printf("Invalid input\n");
           }
       }
       return 0;
       
           }