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

#define MAX 1000

typedef struct {
    int taskID;
    int priority;
} Task;

Task heap[MAX];
int heapSize = 0;

// Swap two tasks
void swap(Task *a, Task *b) {
    Task temp = *a;
    *a = *b;
    *b = temp;
}

// Heapify up
void heapifyUp(int index) {
    if (index == 0) return;
    int parent = (index - 1) / 2;
    if (heap[index].priority < heap[parent].priority) {
        swap(&heap[index], &heap[parent]);
        heapifyUp(parent);
    }
}

// Heapify down
void heapifyDown(int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int smallest = index;

    if (left < heapSize && heap[left].priority < heap[smallest].priority)
        smallest = left;
    if (right < heapSize && heap[right].priority < heap[smallest].priority)
        smallest = right;

    if (smallest != index) {
        swap(&heap[index], &heap[smallest]);
        heapifyDown(smallest);
    }
}

// Insert task into heap
void addTask(int taskID, int priority) {
    // Check for invalid input: negative priority or duplicate taskID
    if (priority < 0) {
        printf("Invalid input\n");
        return;
    }
    for (int i = 0; i < heapSize; i++) {
        if (heap[i].taskID == taskID) {
            printf("Invalid input\n");
            return;
        }
    }

    heap[heapSize].taskID = taskID;
    heap[heapSize].priority = priority;
    heapifyUp(heapSize);
    heapSize++;
    printf("Task Added: %d\n", taskID);
}

// Extract task with highest priority (smallest priority value)
void getTask() {
    if (heapSize == 0) {
        printf("No task available\n");
        return;
    }
    printf("Task with Highest Priority: %d\n", heap[0].taskID);
    heap[0] = heap[heapSize - 1];
    heapSize--;
    heapifyDown(0);
}

int main() {
    int n;
    scanf("%d", &n); // number of operations

    for (int i = 0; i < n; i++) {
        char operation[20];
        scanf("%s", operation);

        if (strcmp(operation, "Task") == 0) {
            char subOperation[20];
            scanf("%s", subOperation);

            if (strcmp(subOperation, "Added:") == 0) {
                int taskID, priority;
                scanf("%d %d", &taskID, &priority);
                addTask(taskID, priority);
            } else if (strcmp(subOperation, "with") == 0) {
                char tmp[20];
                scanf("%s", tmp); // "Highest"
                scanf("%s", tmp); // "Priority:"
                getTask();
            } else {
                printf("Invalid input\n");
            }
        } else {
            printf("Invalid input\n");
        }
    }
    return 0;
}