#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<ctype.h>
#define MAX 1000

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

Task heap[MAX];
int size = 0;
int capacity=0;



void swap(Task* a, Task* b) {
    Task temp = *a;
    *a = *b;
    *b = temp;
}


void heapifyUp(int index) {
    while (index>0){
        int parent=(index-1)/2;
        if (heap[parent].priority>heap[index].priority){
            swap(&heap[parent],&heap[index]);
            index=parent;
        } else{
            break;
        }
}
}
void heapifyDown(int index){
    while(2*index+1<size){
        int left=2*index+1;
        int right=2*index+2;
        int smallest=index;
        if(heap[left].priority<heap[smallest].priority){
            smallest=left;
        }
        if(right<size&&heap[right].priority<heap[smallest].priority){
            smallest=right;
            
        }
        if(smallest!=index){
            swap(&heap[index],&heap[smallest]);
            index=smallest;
            
        }else{
            break;
        }
    }
}
int isValidInput(int taskID,int priority){
    return taskID>=0&&priority>=0;
    
}

void insert(int taskID, int priority) {
    
    
    heap[size].taskID = taskID;
    heap[size].priority = priority;
    heapifyUp(size);
    size++;
}
    

void clearInputBuffer(){
    int ch;
    while((ch=getchar())!='\n'&&ch!=EOF);
}

int main(){
    int n;
    char line[100];
    heap=malloc(INITIAL_CAPACITY * sizeof(Task));
    if(!heap){
        perror("Failed to allocate memory for heap");
        return EXIT_FAILURE;
        }
        capacity=INITIAL_CAPACITY;
    if(!fgets(line,sizeof(line),stdin)||sscanf(line,"%d",&n)!=1||n<=0||n>capacity){ 
            printf("Invalid number of tasks.\n");
            free(heap);
            return EXIT_FAILURE;
    }
    for(int i=0;i<n;i++){
        if(!fgets(line,sizeof(line),stdin)){
            printf("Invalid input\n");
            continue;
        }   
        char* ptr=line;
        char* end;
        int taskID=strtol(ptr,&end,10);
        
    
        int priority=strtol(end,&end,10);
        while(isspace(*end)) end++;
        if(*end!='\0'&&*end!='\n'){
            printf("Invalid input format\n");
            continue;
        }
        if(!isValidInput(taskID,priority)){
            printf("Invalid input for taskID %d or priority %d\n",taskID,priority);
            continue;
            
            
        }
        insert(taskID,priority);
        i++;
    }
    if(size>0){
        printf("Task with Highest Priority: %d\n",heap[0].taskID);
    }else{
        printf("No valid tasks were added.\n");
    }
    
    free(heap);
    return 0;
        
    }