• input
  The first line of the input file contains an integer number N — the number of pairs you should build cartesian tree out of (1 ≤ N ≤ 50 000). The following N lines contain two numbers each — given pairs (ki, ai). For each pair |ki|, |ai| ≤ 30 000. All main keys and all auxiliary keys are different, i.e. ki ≠ kj and ai ≠ aj for each i ≠ j.

• output
  On the first line of the output file print YES if it is possible to build a cartesian tree out of given pairs or NO if it is not. If the answer is positive, on the following N lines output the tree. Let nodes be numbered from 1 to N corresponding to pairs they contain as they are given in the input file. For each node output three numbers — its parent, its left child and its right child. If the node has no parent or no corresponding child, output 0 instead.

• example

1. input
   7
   5 4
   2 2
   3 9
   0 5
   1 3
   6 6
   4 11

2. output
   YES
   2 3 6
   0 5 1
   1 0 7
   5 0 0
   2 4 0
   1 0 0
   3 0 0

• my current code

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

struct Node {
    int k, a;
    int index;
    struct Node* left, * right, * parent;
};

// function prototype
int compare(const void* a, const void* b);
void printNode(struct Node* nodes, int i);

int main() {
    int n;
    scanf_s("%d", &n);
    struct Node* nodes = (struct Node*)malloc(n * sizeof(struct Node));

    for (int i = 0; i < n; i++) {
        scanf_s("%d %d", &nodes[i].k, &nodes[i].a);

        nodes[i].index = i;
        nodes[i].left = nodes[i].right = nodes[i].parent = NULL;
    }
    qsort(nodes, n, sizeof(struct Node), compare); // sort nodes based on k for BST property

    int top = -1; // top is variable of stack
    struct Node** stack = (struct Node**)malloc(n * sizeof(struct Node*));

    for (int i = 0; i < n; i++) {
        struct Node* popped = NULL;
        while (top >= 0 && stack[top]->a > nodes[i].a) {
            popped = stack[top--];
        }
        if (top >= 0) {
            stack[top]->right = &nodes[i];
            nodes[i].parent = stack[top];
        }
        if (popped) {
            nodes[i].left = popped;
            popped->parent = &nodes[i];
        }
        stack[++top] = &nodes[i];
    }
    printf("YESn");
    for (int i = 0; i < n; i++) {
        printNode(nodes, i);
    }
    free(nodes);
    free(stack);
    return 0;
}

int compare(const void* a, const void* b) {
    // If negative, first value > second value
    // If 0, first value == second value
    // If positive, first value < second value
    return ((struct Node*)a)->k - ((struct Node*)b)->k;
}

void printNode(struct Node* nodes, int i) {
    if (nodes[i].parent) {
        printf("%d ", nodes[i].parent->index + 1);
    }
    else {
        printf("0 ");
    }

    if (nodes[i].left) {
        printf("%d ", nodes[i].left->index + 1);
    }
    else {
        printf("0 ");
    }

    if (nodes[i].right) {
        printf("%dn", nodes[i].right->index + 1);
    }
    else {
        printf("0n");
    }
}

• my current result

1. input
   7
   5 4
   2 2
   3 9
   0 5
   1 3
   6 6
   4 11

2. output
   YES
   5 0 0
   2 4 0
   0 5 1
   1 0 7
   3 0 0
   2 3 6
   1 0 0