#include<stdio.h>
#include<stdlib.h>
typedef struct{
    int taskID;
    int priority;
} Task;
typedef struct{
    Task* tasks;
    int size;
    int capacity;
} MinHeap;
MinHeap* CreateMinHeap(int capacity){
    MinHeap* heap=(MinHeap*)malloc(sizeof(MinHeap));
    heap->capacity=capacity;
    heap->size=0;
    heap->tasks=(Task*)malloc(capacity* sizeof(Task));
    return heap;
}
void swap(Task* a, Task*b){
    Task temp=*a;
    *a=*b;
    *b=temp;
}
void insert(MinHeap* heap, int taskID, int priority){
    if(taskID<0 || priority<0){
        printf("Invalid Input\n");
        return;
    }
    if(heap->size>=heap->capacity){
        printf("Heap Full\n");
        return;
    }
    heap->tasks[heap->size].taskID=taskID;
     heap->tasks[heap->size].priority=priority;
     int current=heap->size++;
     while (current !=0 && heap-> tasks[current].priority<heap->tasks[(current-1)/2].priority){
         swap(&heap->tasks[current], &heap->tasks[(current-1)/2]);
         current=(current-1)/2;
     }
     printf("Task Added: %d\n", taskID);
    }
    Task extractMin(MinHeap* heap){
        if(heap->size==0){
            Task t={-1, -1};
            return t;
        }
        Task root=heap->tasks[0];
        if(heap->size>1){
            heap->tasks[0]=heap->tasks[--heap->size];
            int current=0;
            while(current<heap->size){
                int left=current*2+1;
                int right=current*2+2;
                if(left>=heap->size) break;
                int smallest=left;
                int(right)<heap -> size && heap->tasks[right].priority<heap->tasks[left].priority){
                    smallest=right;
            }
            if(heap->tasks[current].priority<=heap->tasks[smallest].priority) break;
            swap(&heap->tasks[current],&heap->tasks[smallest]);
            current=smallest;
            }
    } else {
        heap->size--;
    }
    return root;
    }
    int main(){
        int n;
        scanf("%d", &n);MinHeap*heap=CreateMinHeap(n);
        for(int i=0;i<n;i++){
            int taskID, priority;
            scanf("%d %d", &taskID, &priority);
            insert(heap, taskID, priority);
        }
        Task highestPriorityTask=extractMin(heap);
        if(highestPriorityTask.taskID !=1){
            printf("Task with Highest Priority:%d\n", highestPriorityTask. taskID);
        }else {
            printf("No valid  tasks available.\n");
    }
    return 0;
    }